BOJ 12852 - 1로 만들기 2 (https://www.acmicpc.net/problem/12852)
백준에서 DP를 풀어본 사람들은 한번쯤 접해봤을법한 1로 만들기 문제의 응용판이다.
최적해를 구하는 것으로 끝나는 것이 아니라, 최적해에 대한 스텝도 출력해줘야해서 조금 까다롭다.
요즘 이런 류의 문제를 계속 풀어보고 있는데 너무 재밌어서 앞으로도 더 많이 풀어봐야겠다.
간단 풀이 1
탑다운 방식으로 접근해보자.
N에서 시작하여 1까지 내려가면서 최적횟수를 저장하고, 그 때마다 별도 배열에 현재 숫자가 어느 위치에서 왔는지를 저장해주면 된다.
예를 들어 현재 숫자가 9인 경우, 여기서 3을 나누면 3이 된다는 사실은 자명하고 현재 상태에서 3으로 갈 수 있는 가장 빠른 방법이다. 어느 위치에서 왔는지 저장하는 배열을 before 라고 하면 before[3] = 9가 된다.
모든 최적값을 저장했으면 이제 1에서 N으로 올라가면서 스택에 스텝들을 저장하면 된다.
그 후에 스택에서 하나씩 빼서 출력하면 완료.
간단 풀이 2
바텀업 방식으로 접근해보자.
1에서 시작하여 N-1까지 올라가면서 (i * 3), (i * 2), i + 1 지점에 최적횟수를 저장해나가면 된다.
풀이 1 방식에서는 올바른 순서로 출력하기 위해 스택을 썼지만, 바텀업 방식 같은 경우는 (i * 3), (i * 2), i + 1 지점에 이전 스텝을 저장할 것이기 때문에 그냥 N부터 시작해서 1이 될때까지 내려가면서 스텝들을 출력해주면 된다.
예를 들어 N이 10이었다면, before 배열은 아래와 같다.
[0, 0, 1, 1, 2, 4, 2, 6, 4, 3, 9]
내가 구현한 기준으로 출력에 대한 코드는 아래와 같다.
while(n > 0) {
sb.append(n).append(" ");
n = before[n];
}
-
출력하는 과정을 N = 10에서 시작해보자.
-
먼저 현재 숫자인 10을 출력하고,
N = before[N]을 대입하여 다음 스텝으로 내려간다. -
before[10] = 9이므로 현재 N = 9이다. 9를 출력하고 다음 스텝으로 내려간다. -
before[9] = 3이므로 현재 N = 3이다. 3을 출력하고 다음 스텝으로 내려간다. -
before[3] = 1이므로 현재 N = 1이다. 1을 출력하고 다음 스텝으로 내려간다. -
before[1] = 0이었으므로 while문에서 벗어나게된다.
마무리
참고로 이런 문제에 대한 가이드는 종만북 (알고리즘 문제 해결 전략) 1권 9.1에 있으므로 그 쪽을 읽어보는 것도 매우 도움이 된다.
다음에는 지난 주에 많은 시간을 들여 풀었던 경찰차(KOI 2003 중등부) 문제를 올려봐야겠다.