HwangHub

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🤔 Intuition 처음에는 DP라고 생각했다. 근데 아니였다. DP가 성립하려면 2가지 조건을 성립해야 한다. 부분 반복 문제 (Overlapping subproblem) : 어떤 문제가 부분 문제로 쪼개질 수 있는지 최적 부분 구조 (optimal substructure) : 부분 문제에서 구한 최적의 답이, 원래 문제의 최적의 답과 동일한지 이 문제를 통해 위 조건을 검토해보자면, 부분 반복은 된다. 왼쪽으로 한칸, 오..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 출발점부터 도착점까지 이동할 때 "최단 거리"를 구해야 함 격자 공간 위에서 이동 조건이 존재 이동할 때마다 가중치(이동 시간)는 기본 1 하지만 소용돌이 구간은 가중치가 달라짐 (시간이 더 오래 걸림) n은 2 이상 15 이하 위 조건을 고려했을 때, 모든 간선의 가중치가 양수이며 최단거리를 구하는 것이므로 다익스트라로 푸는 것을 먼저 고려해봤다. 다만, 아직 다익스트라가 익숙치 않은 탓에 우선순위 큐는 사용하지 않았고, 기본적인 BFS 로직 위에 최단 거리로 각 노드를 갱신하는 로직만 추가하여 구현하였다. 이렇게 할 경우에는 다익스트라의 시간복잡도가..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 해석 이 문제는 시작 노드와 끝 노드가 정해져 있는 상태에서, 최단 거리를 구하는 문제이므로 기본적으로 BFS를 이용한 그래프 알고리즘 문제일 것이라 가정하였다. 여기서 처음에 문제를 이해할 때에는 가중치가 양수라 생각했기에 다익스트라 알고리즘이 적절할 것이라 보았다. 다익스트라는 시간복잡도가 O(ElogV)이므로 N = 100인 문제에서는 문제 없다. -- 근데 나중에 생각하니, 가중치의 범위에 대한 언급이 없어서 문제가 명확하게 조건을 제시하고 있는 것 같지는 않다. 근데 출제 의도는 다익스트라 였던 것 같다. 다익스트라 알고리즘은 특정 노드를 기준으로, 이와..