1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
피보나치수열을 구하는 것만큼이나 간단한 동적 계획법 문제이다. 동적 계획법은 상향식 계산과, 하향식 계산으로 구분되는데, 오늘은 1697번 문제를 상향식 구현을 해본다.
수빈이와 동생이 놀고 있는 점들을 아래와 같이 나타냈다.
상향식 동적 계획법 (= tabulation) 이므로 모든 경우의 수를 다 구하며 정답을 향해 갈 것이다.
규칙은 아래와 같다.
- (규칙 A) 현재 시간에 탐색된 점들을 저장한다. (큐 등을 이용)
- (규칙 B) 저장된 점들을 하나씩 꺼내어 +1 / -1 / *2 연산을 해준다.
- (규칙 C) 규칙 B에 의해 연산된 결과에 해당하는 점이 기존에 탐색되지 않았다면, 해당 점에 현재시간 +1의 값을 준다.
- (규칙 D) 목표에 도착할 때까지 A~C의 규칙을 반복한다.
최초 시작 시 현재 시간은 0이므로 시작점에는 0이 들어간다. 그 뒤 큐 등에 시작점인 5번을 넣어준다.
규칙 B 에 의해 4, 6, 10번 점이 계산되었고, 규칙 C에 의해 1의 값들이 들어간다.
다시 규칙 A에 의해 4, 6, 10번 점들은 큐 등에 저장된다.
규칙 D에 의해 반복하며 4, 6, 10 점들은 각각 (3, 8), (7, 12), (9, 11) 점 들을 탐색하게 한다.
이러한 방식으로 목표지점까지 가는데 소요되는 횟수 (=시간)을 구할 수 있다.
이와 같이 시작 지점부터 진행하여 모든 경우의 수에 대하여 탐색을 하되, 동적 계획법을 사용하는 방식이 상향식 DP인 tabulation이다. 개인적으로 memoization과 tabulation 간에 어떤 것이 더 좋다는 느낌은 없고 문제에 적합한 방식으로 푸는 편인데 간단한 PS 문제나 기업 코딩 테스트 수준에서는 어떤 것을 선택해도 정답을 띄워주는 편 인 것 같다.
code
GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지
알고리즘 온라인 저지. Contribute to YoungWoo93/algorithmOnlineJudge development by creating an account on GitHub.
github.com
조만간 메모이제이션이 더 적합한 문제를 하나 풀고 (아마 백준 1003번 문제를 풀 것 같다) 하향식으로 동적 계획법을 처리하는 글도 써서 상호 링크해야겠다.
'알고리즘 온라인 저지 > BOJ' 카테고리의 다른 글
| BOJ 2014 소수의 곱 (0) | 2022.01.18 |
|---|---|
| BOJ 1916 최소비용 구하기 (0) | 2022.01.12 |
| BOJ 1002번 터렛 (0) | 2022.01.11 |
| BOJ 1753번 최단경로 (0) | 2022.01.11 |
| BOJ 1644 소수의 연속합 (0) | 2022.01.10 |
