[DP] [BOJ 1463] 1로 만들기

 

1463번: 1로 만들기

문제

 

어떤 자연수 N에 대해서 세 가지의 연산을 할 수 있다.

1. 3으로 나누어 떨어지면 나눈다.

2. 2로 나누어 떨어지면 나눈다.

3. 1을 뺀다.

 

임의의 자연수는 이 연산을 반복할 경우 1로 만들 수 있다.

어떤 자연수 N에 대해서, 1로 만들기 위한 연산의 최소 횟수를 구하는 문제.

 

무식하게 접근하기

 

우선 가장 무식한 방법은 모든 숫자에 대해서 세 가지 연산을 해보는 것이다.

 

완전 탐색으로 풀 때, 그래프를 그려보자.

 

하지만, 각각의 숫자에 대해서 최대 3개의 연산을 할 수 있으므로, 시간복잡도는 $O(3^N)$가 된다.

근데 N = 100,000이므로 절대로 풀 수가 없다. 제출해보니 메모리 초과가 뜬다.

 

왜 DP로 풀 수 있는가?

 

DP로 풀 수 있으려면, 

1. 문제를 작은 문제로 분할할 수 있고

2. 부분 문제의 정답으로 큰 문제를 해결할 수 있어야 한다.

그렇다면 여기서 중복되는 부분문제(Overlapping Subproblem)는 무엇인가?

 

위의 그림에서는 1, 2, 3, 4가 여러 번 나오게 된다. (즉, 1, 2, 3, 4의 연산 횟수를 구하는 부분문제가 중복된다.)

그리고 1, 2, 3, 4에 대한 정답을 새로 또 구하게 된다. 따라서 N보다 작은 문제들에 대하여 정답을 저장(메모이제이션, Memoization)하면 같은 문제를 중복해서 풀지 않아도 된다.

 

즉, d[i-1], d[i / 3], d[i / 2]중 가장 작은 것을 고르고, 1을 더해주면 답을 구할 수 있다.

 

그럴 때의 시간 복잡도는 어떻게 될까?

1, 2, 3, ..., N에 대한 정답을 알고있는 경우, N+1에 대한 정답은 $O(1)$만에 구할 수 있다. 그렇다면

1에 대한 정답 (0)만 알고 있다면, 임의의 숫자 N에 대한 정답은 $O(N)$만에 구할 수 있다.

 

시간복잡도가 $O(3^N)$에서 $O(N)$로 대폭 개선되었다!

그래프를 그려보니 이 문제는 피보나치와 매우 유사한 문제같다. 

 

구현