[BOJ/백준] 1463번 1로 만들기 (Python 파이썬)

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

1463번: 1로 만들기

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.15 초	128 MB	215882	70677	45247	32.201%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1 

2

예제 출력 1 

1

예제 입력 2 

10

예제 출력 2 

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

 

---

풀이

처음에는 greedy하게 (1)먼저 3으로 나눠보고 (2)안되면 2로 나눠보고 (3)안되면 1을 빼는 식으로 생각했었지만 힌트에서 주어진 것처럼 무작정 연산의 순위를 적용할 수는 없습니다. 위 순서대로 라면 10이 주어졌을 때 먼저 2를 나누기 때문에 10->5->4->2->1 순서로 진행되기 때문에 정답이 될 수 없습니다.

따라서 항상 최적의 해를 구하는 DP를 사용하여 작은 부분 문제부터 풀면서 올라가겠습니다.
dp라는 리스트는 인덱스 i에 대해서 "i를 1로 만들기 위한 연산의 최소 횟수"를 저장합니다.

편의를 위해 0이 아닌 1부터 시작하도록 구성하였고, dp[1]은 0입니다.(연산을 하지 않아도 되기 때문)
따라서 모두 0으로 초기화한 뒤, 2번부터 문제를 풀어갔습니다.

N = int(input())

# 연산 횟수 저장 -> 앞에서 구한 값을 저장하고 후에 사용하기
dp = [0]*(N+1)  # 인덱스 맞추기 위해 N+1

for i in range(2, N+1):
    # case 1. 1을 빼는 연산 ex) 10이면, 9인 경우에 1 더한 값
    dp[i] = dp[i-1] + 1

    # case 2. 2를 나누는 연산. case1과 비교하여 작은 값을 저장
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    # case 3. 3을 나누는 연산. case1, case2와 비교하여 작은 값을 저장
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[N])

앞에서 언급했듯이 무작정 연산의 순위를 정하지 않고 각 경우에 대해서 가장 최솟값을 가지는 경우를 저장하도록 했습니다.

위 코드는 큰 틀에서는 밑에서 올라가지만, dp를 연산하는 곳에서는 top-down방식입니다.