BOJ 1056 : 수

https://www.acmicpc.net/problem/1056

1056번: 수

 

누가 봐도 DP를 이용하는 것이다.

 

dp[i] = i를 만드는데의 최소 연산 수

. 

a^k<=n<=a^(k+1)이라고 하자.

이때 두 가지 경우가 생기는데, 3번 연산 후 (a^(k+1)-n)번만큼 빼기 연산을 하거나 (n-a^k)번만큼 빼기 연산을 적용시킬 수 있다. 이때 특정 a에 대해 최소 연산 횟수는 저 두 가지 경우와 1번 연산만을 이용했을 경우 중 최솟값이 된다.

이때 k가 적어도 62까지 가능하므로 이를 통해 DP를 돌리자.

 

dp[i] = min(dp[i], n-1, dp[a]+|a^k-n|+1, dp[a]+|a^(k+1)-n|+1)

 

적절한 a를 찾는 것은 이분탐색을 활용하여 풀 수 있다.

 

오버플로우에 주의하길 바란다. 오버플로우를 방지하기 위해 각 k마다 a^k<=(long long범위의 최댓값)을 만족하는 최대의 a를 배열에 저장하는 방식을 이용하였고, 이는 이분탐색으로 가능하다.

 

코드