[백준] 1463번: 1로 만들기 - Python

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

1463번: 1로 만들기

 

 

---

 

 

 

 

---

 

풀이 과정

 

제가 저 문제를 처음 접했을 때 들었던 생각 중 하나는

 

1. 3으로 나누어 떨어지면 가장 먼저 3으로 나눈다.
2. 3으로 나누어 떨어지지 않고, 2로 나누어 떨어지면 2로 나눈다.
3. 2과 3 모두 나누어 떨어지지 않으면 1을 뺀다.

이렇게 생각하고 풀이를 하려고 했는데 예제 입력에 보이듯이 10을 입력하면 3이 나와야 합니다.

제가 생각한 풀이로는 10 -> 5 -> 4 -> 3 -> 1의 순서를 거쳐서 4번 만에 1에 도달하는 것으로 답이 나오게 됩니다.

하지만 연산을 최소로 사용하려면 10 -> 9 -> 3 -> 1의 순서로 3번 만에 1에 도달하게 됩니다. 제가 처음 생각했던 풀이는 틀린 방법인 거죠. 1에 도달은 할 수 있으나 연산이 최소 횟수가 되지 않으니까요.

 

 

그래서 저는 DP를 이용해서 풀이 공식을 세워보았습니다.

 

입력으로 1이 들어왔을 때는 1로 만들기 위해서 연산을 할 필요가 없죠? 연산 횟수는 0이고 정답으로 0이 출력되어야 합니다. 

2를 1로 만들기 위해서 필요한 연산은 1번(2 -> 1)

3을 1로 만들기 위해서 필요한 연산은 1번(3 -> 1)

4를 1로 만들기 위해서 필요한 연산은 2번(4 -> 2 -> 1 or 4 -> 3 -> 1)

5를 1로 만들기 위해서 필요한 연산은 3번(5 -> 4 -> 2 -> 1 or 5 -> 4 -> 3 -> 1)

 

이제 6의 경우를 보겠습니다. 6이 1이 되기 위해서 할 수 있는 연산은 3종류입니다.

1. 6에서 3을 나누어서 2로 만들기
2. 6에서 2를 나누어서 3으로 만들기
3. 6에서 1을 빼서 5로 만들기

즉, 숫자 6에서 3종류의 연산으로 만들 수 있는 숫자는 2, 3, 5입니다.

2는 1을 만들기 위해서 연산이 1번 필요하고, 3 또한 1을 만들기 위해서 연산이 1번 필요하고, 5는 1을 만들기 위해서 연산이 3번 필요합니다. 그럼 당연히 연산의 최소 횟수를 구하기 위해선 6에서 2 or 3으로 만들어야겠죠?

(2 or 3으로 만들기 위한 연산 1번) + (1로 만들기 위한 연산 1번) = 총 2번의 연산이 필요하게 됩니다.

 

이렇게 기존에 계산했던 값을 사용하는 알고리즘 풀이방식이 다이나믹 프로그래밍(DP)입니다.

 

위와 같은 방식으로 코드를 작성하면 아래와 같이 작성할 수 있습니다.

X = int(input())

dp = [0] * 1000001
dp[1] = 0

for i in range(2, 1000001):
    if i % 3 == 0 and i % 2 == 0:
        dp[i] = min(dp[i - 1], dp[i // 2], dp[i // 3]) + 1
    elif i % 3 == 0:
        dp[i] = min(dp[i - 1], dp[i // 3]) + 1
    elif i % 2 == 0:
        dp[i] = min(dp[i - 1], dp[i // 2]) + 1
    else:
        dp[i] = dp[i - 1] + 1

print(dp[X])

 

 

i가 6일 때, 6은 3과 2 모두 나누어 떨어지므로 아래의 코드를 수행하게 됩니다.

dp[i] = min(dp[i - 1], dp[i // 2], dp[i // 3]) + 1 

 

 

i에 숫자를 대입해 보면 위에 설명했던 방식과 마찬가지의 결과를 볼 수 있습니다

dp[6] = min(dp[5], dp[3], dp[2]) + 1

 

 

위와 같이 소스 코드를 작성하면 1,000,000을 1로 만드는데 필요한 최소 연산 횟수까지 구한 다음에 입력받은 X를 dp에 대입해서 정답을 출력하게 됩니다.