[BOJ] 1463: 1로 만들기(python)

1. 문제

문제 링크

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

위의 3가지 연산 중 한 번에 하나의 연산을 사용하여 특정 수를 1로 만들 때,
연산을 사용하는 횟수의 최솟값을 구하는 문제이다.

2. 문제 풀이

숫자 2를 1로 만드는 방법은 아래와 같다.

1. 2 → 1 (1을 빼는 방법/2로 나누는 방법)

숫자 3을 1로 만드는 방법을 생각해보자.

1. 3 → 1 (3으로 나누는 방법) = 1
2. 3 → 2 → 1 (1씩 빼는 방법) = 2 = 1 + 1

또, 숫자 4를 1로 만드는 방법을 생각해보자.

1. 4 → 2 → 1 (2로 2번 나누는 방법)
2. 4 → 3 → 2 → 1 (1씩 빼는 방법)
3. 4 → 3 → 1 (1을 뺀 후, 3으로 나누는 방법) = 3 = 2 + 1

위 방법들을 보면

1을 빼는 연산보단, 2 또는 3으로 나누는 연산을 사용할 때 연산사용 횟수가 작다.
1을 빼는 연산의 경우는 구하고자 하는 정수 X보다 1이 작은 정수의 최소 연산 사용 횟수에 1을 더한 값이다.

는 사실을 알 수 있다.

즉, 구하고자 하는 정수보다 1이 작은 정수의 최소 연산 횟수 + 1과,
구하고자 하는 정수가 2나 3으로 나누어 떨어지는 경우 나누었을 때의 정수의 최소 연산 횟수 + 1을 비교하여 더 작은 것을 택하면 되는 것이다.

이를 구하기 위해서는 2부터 순차적으로 최소 연산 횟수를 찾아야 하며,
따라서 DP를 사용하여 문제를 해결하였다.

3. 소스코드

x = int(input())    # 입력받은 정수 X

d=[0]*(x+1)    # DP 테이블

for i in range(2,x+1): 
    # a: 1을 빼는 경우 먼저 연산
    d[i]=d[i-1]+1 
    
    # 2나 3으로 나누어 떨어지는 경우, 나누었을 때의 값 + 1과 a 값 비교 후 작은 값 할당
    if i%2==0: 
        d[i]=min(d[i],d[i//2]+1)
        
    if i%3==0:
        d[i]=min(d[i],d[i//3]+1)
       
print(d[x])