코딩 코딩

경로 역추적

• [BOJ] 13913 숨바꼭질 4

  PS/BOJ 2020. 7. 16. 18:26

  https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 알고리즘: BFS 시간복잡도: O(V+E) BOJ 1697의 업그레이드 버전이다. https://moon323.tistory.com/16 이동하는 경로를 출력하는 부분이 추가되었다. 경로 추적은 이전에 BOJ 12852 1로 만들기2 https://moon323.tistory.com/6 에서 DP 경로 역추적을 하는 방식이랑 비슷하다. BFS에서 a->b로 ..

  Read More
• [BOJ] 12852 1로 만들기 2

  PS/BOJ 2020. 7. 15. 15:18

  https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 알고리즘: DP, DFS 시간복잡도: O(logN) 1463 1로 만들기에서 경로 추적을 추가한 문제. https://moon323.tistory.com/5 접근: Dp 경로 추적 문제들이 늘 그렇듯 점화식에서 참고한 부분문제의 성분을 저장해주면 됨. ex) v[] : 경로 추적 배열 D[X] = Min(D[X/2] + X%2 + 1, D[X/3] + X%3 +1) 에서 D[X/2] 부분을 가져왔으면 v[X] = 2로 표시, D[X/3] 부분을 가져왔으면 v[X] = 3 으로 표시 v를 참고하여 역추적..

  Read More