★ solved.ac 난이도 : S1
(작성 시점 기준)
[문제 본문 링크]
12852번: 1로 만들기 2
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.
www.acmicpc.net
이 문제는 일반적인 동적 계획법(DP) 문제이며, BOJ #1463 (1로 만들기) 문제에서 역추적을 추가한 문제입니다.
먼저 크기가 100만 이상인 충분한 정수 배열 2개를 만듭니다.
(배열의 이름은 dp로 설정하며, 정답 계산용[0]과 역추적용[1]으로 구분합니다.)
입력이 1이면 연산이 필요하지 않으므로 정답은 0입니다. (dp[1][0] = dp[1][1] = 0)
2 이상의 입력에 대해서는 문제의 조건에 따라 3가지로 생각할 수 있습니다.
경우 1. x가 3으로 나누어 떨어지면서 dp[i/3][0] < dp[i][0]인 경우
dp[i][0] = dp[i/3][0]+1로 바꾸고, dp[i][1]에 i/3을 저장합니다.
(여기에서 +1은 1번의 추가 연산을 의미합니다.)
경우 2. x가 2로 나누어 떨어지면서 dp[i/2][0] < dp[i][0]인 경우
dp[i][0] = dp[i/2][0]+1로 바꾸고, dp[i][1]에 i/2를 저장합니다.
경우 3. 그렇지 않은 경우
dp[i][0] = dp[i-1][0]+1로 바꾸고, dp[i][1]에 i-1을 저장합니다.
최종적으로 dp[n][0]을 출력하고, dp[n][1]부터 역추적한 결과를 출력하면 됩니다.
[BOJ에서 코드 보기]
공유 소스 보기
www.acmicpc.net
★ 틀린 점이 있다면 알려주세요~!