[백준/Python] 1로 만들기

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

1463번: 1로 만들기

n = int(input())
dp = [0] * (n+1)

for i in range(2, n+1):
	dp[i] = dp[i-1] + 1 # 2와 3으로 나누어 떨어지지 않는 경우 무조건 1을 빼줘야 하므로 횟수를 추가한다

	if i % 2 == 0: # 2로 나누어 떨어지는 경우
		dp[i] = min(dp[i], dp[i//2] + 1)
	if i % 3 == 0: # 3으로 나누어 떨어지는 경우
		dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[n])

이 문제는 그렇게 어렵지 않은 dp문제인 것 같았지만 어떻게 구현해야할지 잘 생각나지 않았다. 그래서 생각하는 과정을 자세히 써보려한다.

 

먼저 이 문제가 dp인 이유는 예전에 구해놓았던 값을 가져다 쓸 수 있기 때문이다. 예를 들어, 9와 3의 경우를 보면 3 = 3 / 3 = 1 의 과정을 거쳐 1번의 연산을 수행한다. 9는 9 = 9 / 3 / 3 = 1 의 과정을 거쳐 2번의 연산을 수행한다. 이 때 9는 3의 연산과 중복되는 부분이 있다. 그래서 중복되는 부분 (= 예전에 구해놓았던 값)을 가져다 쓰는 것이다. 이것을 알면 점화식은 쉽게 구할 수 있다. 

-> 2와 3으로 나누어 떨어지는 경우, 점화식은 dp[i] = min(dp[i], dp[i// 2 or 3] + 1) 이다.

 

1을 빼줘야 하는 경우는 2와 3으로 나누어 떨어지지 않는 경우다. 따라서 2와 3으로 나누어 떨어지지 않는다면 무조건 1을 빼줘야 하므로 dp[i] = dp[i-1] + 1 하여 1을 뺀 연산의 횟수를 추가해준다. 

 

그럼 왜 1을 빼고 시작하는 것인가? 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되기 때문이다. 예를 들어, 6의 경우를 살펴보면 dp[5] = 3 이므로 1을 빼고 시작하면 dp[6] = dp[5] + 1 = 4 가 된다. 그 다음 연산을 수행하는데 6는 2로 나누어 떨어지므로 dp[6] = min(dp[6], dp[3] + 1) = min(4, 2) = 2 가 된다. 6은 3으로도 나누어 떨어지므로 dp[6] = miin(dp[6], dp[2] + 1) = min(2, 2) = 2 가 된다. 이렇게 어차피 교체되기 때문에 1를 빼고 시작한다.

 

그리고 3가지 연산을 다 해보는 이유는 어떤 연산이 최적의 연산인지 알 수 없기 때문이다.