BOJ 1463: 1로 만들기- 파이썬(Python)

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

<접근 방법>

문제에서 제시한 방법을 적용하여 1로 만드는 최소 횟수를 계산하는 문제이다. DP를 이용하여 문제를 해결할 수 있다.

예시 상황으로 $N = 10$일 때를 가정해 보자.

 

10은 2로 나누어 떨어지기도 하고, 1을 빼는 연산도 수행할 수 있을 것이다. 그러면 2가지 경우를 고려해서 최솟값을 계산해야 한다.

 

우선 1부터 차례대로 규칙을 확인해 보면 답을 찾을 수 있을 것이다.

아래의 배열을 구성하자. 그러면 1은 자명하게 0이 될 것이다.

N	1	2	3	4	5	6	7	8	9	10
min	0	???	???	???	???	???	???	???	???	???

 

 

이제 2일 때를 계산해 보자. 2는 2로 나누어 떨어지고, 1을 뺄 수 있다. 그러면 아래와 같이 계산할 수 있을 것이다.

(N = 2일 때 최솟값) = min(arr[2 // 2] + 1, arr[2 - 1] + 1) = min(arr[1] + 1, arr[1] + 1) = min(0 + 1, 0 + 1) = 1

 

따라서 $N = 2$일 때에는 1이 된다.

 

이번에는 $N = 3$일 때를 고려해 보자. 3은 3으로 나누어 떨어지고, 1을 뺄 수 있다. 그러면 아래와 같이 계산할 수 있을 것이다.

(N = 3일 때 최솟값) = min(arr[3 // 3] + 1, arr[3 - 1] + 1) = min(arr[1] + 1, arr[2] + 1) = min(0 + 1, 1 + 1) = 1

 

따라서 $N = 3$일 때에는 1이 된다.

 

결과적으로, 위의 연산을 모든 N에 대해서 적용하면 아래와 같이 계산될 것이다. 즉, $N = 10$일 때, 최솟값은 3이 된다.

N	1	2	3	4	5	6	7	8	9	10
min	0	1	1	2	3	2	3	3	2	3

 

<소스 코드>

위의 코드를 이용한 전체 소스 코드 구현 결과이다.

import sys

a = int(sys.stdin.readline())
counting = [0] * (10 ** 6 + 1)

for i in range(2, a + 1):
    counting[i] = counting[i - 1] + 1

    if i % 2 == 0:
        counting[i] = min(counting[i], counting[i // 2] + 1)

    if i % 3 == 0:
        counting[i] = min(counting[i], counting[i // 3] + 1)

print(counting[a])