[백준] 1463번 1로 만들기, 파이썬 문제 풀이

문제

백준 1463번 주어진 정수를 특정 연산을 통해 1로 만들 때, 최소한의 연산 횟수를 찾는 문제를 해결했습니다.

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

1463번: 1로 만들기

문제

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

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

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

예시: 10

입력

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

출력

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

예시: 3

 

문제 풀이

정수 N이 주어지면, 3 혹은 2로 나누거나 -1 연산을 해서 1로 만들어야 합니다. 처음 생각할 땐, 연산을 뒤집어서(x2, x3, +1) N을 만드는 방법을 생각해봤습니다. 하지만, 일정한 규칙이 존재하지 않고 항상 반례가 존재했기 때문에, 모든 경우의 수를 확인해야 했습니다.

 

따라서, 모든 경우의 수를 진행하고 최소 연산 횟수를 넘어간다면 가지치기(백트래킹)을 하는 방법을 생각했습니다. 재귀함수를 활용해서 구현했습니다. 하지만, 이 문제의 중요한 점은 제한 시간입니다. 파이썬(pypy3)은 0.7초의 제한 시간이 있습니다. 모든 경우의 수를 확인하기엔 부족한 시간입니다. 최대 입력이 1000000이기 때문에, 연산 3개의 경우의 수를 확인하면 제한 시간을 초과하게 됩니다. 제가 생각한 예시는 통과한 최초 코드는 다음과 같습니다.

INF = 99999999

def cal(n, cnt):
    tmp = [INF]*3

    if(n<=0):
        return INF
    elif(n==1):
        return cnt

    if(n%3==0):
        if(n%2==0):
            tmp[0] = cal(n//3, cnt+1)
            tmp[1] = cal(n//2, cnt+1)
            tmp[2] = cal(n-1, cnt+1)
            cnt = min(tmp)
        else:
            tmp[0] = cal(n//3, cnt+1)
            tmp[1] = cal(n-1, cnt+1)
            cnt = min(tmp)
    elif(n%2==0):
        tmp[0] = cal(n//2, cnt+1)
        tmp[1] = cal(n-1, cnt+1)
        cnt=min(tmp)
    else:
        cnt = cal(n-1, cnt+1)
    return cnt

N = int(input())

result = cal(N, 0)

print(result)

이 코드의 결과는 시간 초과였습니다. 사실, 위에서 말한 내용 중 백트래킹을 하고 있지 않은 상태입니다. 모든 경우의 수를 확인하기 때문에 많은 시간이 필요합니다. 가만히 생각해보니, 재귀 호출을 하게 되면 함수 스택이 쌓여있어 일정 조건에서 return을 해도 이미 연산이 진행된 상태였습니다.

 

따라서, 논리가 잘못되었다고 판단했습니다. 따라서, 방법을 바꾸어 DP(Dynamic Programming)으로 접근했습니다. DP의 핵심은 메모이제이션(Memoization)입니다. 이전 결과를 기억하고 있는 것입니다. DP를 활용하기 위해서는 생각을 바꿔야 했습니다. 바로, N부터 1로 가는 것이 아닌, 1부터 N으로 가는 것입니다. 1~N 사이에 있는 숫자들까지 필요한 연산을 DP에 저장하고 있다가, 더 큰 숫자는 이전의 연산 결과를 활용합니다.

1부터 N까지 가는 과정에서 특정 숫자 i로 도착하기 위해서는 4가지 경우의 수가 존재합니다.

• i가 3으로 나뉘는 경우
• i가 2로 나뉘는 경우
• i가 3과 2 모두 나뉘는 경우
• i가 아무 숫자도 나뉘지 않는 경우

각각의 경우에서 할 수 있는 할 수 있는 연산을 한 숫자의 연산 횟수+1을 하게 되면 i까지 가는데 필요한 연산 횟수입니다. 

예를 들어, i=4 이면 4는 2로 나뉘기 때문에, 2*2 혹은 3+1 로 4를 만들 수 있습니다. 2를 만드는데 필요한 연산 횟수, 3을 만드는데 필요한 연산 횟수 중 최소한의 연산에 *2 혹은 +1 연산 1번 더 하면 4를 만들 수 있습니다. 

해당 DP의 점화식은 다음과 같습니다.

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

 

해당 점화식을 이용한 코드는 다음과 같습니다.

N = int(input())
DP = [0]*(N+1)

for i in range(2,N+1):
    if(i%3==0):
        if(i%2==0): #3, 2 둘 다 나뉘는 경우
            DP[i] = min(DP[i//2], DP[i//3], DP[i-1])+1
        else: # 3으로만 나뉘는 경우
            DP[i] = min(DP[i//3], DP[i-1])+1
    elif(i%2==0): #2로만 나뉘는 경우
        DP[i] = min(DP[i//2],DP[i-1])+1
    else: # 아무것도 나뉘지 않는 경우
        DP[i] =DP[i-1]+1

print(DP[N])

정리

코드로 작성하기 전에 시간 복잡도를 먼저 생각해보는 습관을 들여야할 것 같습니다. 백트래킹으로 먼저 접근했기 때문에 시간이 초과하는 문제가 발생했습니다. DP를 작성할 때, 점화식을 생각해야 합니다. 점화식을 세우지 않고 임의로 판단하면 헷갈리고, 식이 달라지는 문제점이 발생할 수 있습니다.