[BOJ] 백준 1463번 - 1로 만들기 (Python)

문제

문제 바로가기

해결

주어지는 숫자의 범위는 1~1000000이고, 위의 3가지 연산을 활용하여 1로 만들되, 가장 적게 연산을 사용해야 한다.

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

첫 입력 숫자에서부터 1이 되기 전까지 위의 연산을 사용하는데, 당연히 3으로 나누는 것이 빠르게 숫자가 줄어들 것이다.

언뜻 보면 그리디를 활용한 문제인 것 같으니 일단 그리디를 활용하여 문제를 풀기 위해 다음과 같은 코드를 작성하였다.

N = int(input())
cnt = 0

while N != 1:
  if N % 3 == 0:
    N /= 3
    cnt += 1
  elif N % 2 == 0:
    N /= 2
    cnt += 1
  else:
    N -= 1
    cnt += 1
    
print(cnt)

물론 위 코드는 오답이다. 예를 들어 10이 N에 대한 입력으로 들어왔을 때, 위 코드에 의해 10/2, 5-1, 4/2, 2/2 총 4회 실행되는 데 반해, 정답은 10-1, 9/3, 3/3 총 3회 연산이 수행되기 때문이다. 그리디 측면으로 생각하면 절대로 선택할 수 없을 연산인 -1을 선택하여 다음 연산을 더 편하게 하는 것이다. 즉 미래를 내려다 보거나, 완전 탐색으로 가장 적게 연산을 수행하는 방향을 이미 알고 있어야 한다.

하지만 미래를 내려보는 건 물론이거니와, 완전 탐색으로 1.5초 안에 해당 문제를 해결하는 건 불가능한 일, 다이나믹 프로그래밍 기법을 활용해 (3개의 연산) 각각의 케이스마다 메모이즘 방식으로 저장된 최소 수행 횟수를 불러오는 방식을 사용하게 되면 빠른 수행시간 내에 해결할 수 있게 될 것이다.

N = int(input())

d = [0] * 1000001  # d[1] = 0

for i in range(2, N + 1):
  if i % 6 == 0:
    m = min(d[i - 1], d[i // 2], d[i // 3])
    d[i] = m + 1
  elif i % 3 == 0:
    m = min(d[i - 1], d[i // 3])
    d[i] = m + 1
  elif i % 2 == 0:
    m = min(d[i - 1], d[i // 2])
    d[i] = m + 1
  else:
    d[i] = d[i - 1] + 1

print(d[N])

위 코드는 기본적으로 바텀업 방식 다이나믹 프로그래밍을 기반으로 한 코드이며 다음과 같은 방식으로 동작한다.

1. 2부터 N까지 차근차근 리스트에 계산된 값들을 넣어가며 연산의 최솟값을 계산한다.
2. 2와 3 중 어떤 숫자로도 나뉘어지지 않는 숫자는 이전 계산된 i-1의 값에 + 1을 해준다. (1로 빼는 연산을 더하는 것)
3. 2로 나뉘는 숫자는 i-1과 i//2의 값 중 작은 숫자에 + 1을 해준다. (2로 나누는 연산혹은 -1 연산을 더하는 것)
4. 3으로 나뉘는 숫자는 i-1과 i//3의 값 중 작은 숫자에 +1을 해준다. (3로 나누는 연산 혹은 -1 연산을 더하는 것)
5. 2와 3의 최소공배수인 6으로 나뉘는 숫자는 i-1, i//2, i//3의 값 중 작은 숫자에 +1을 해준다. (3로 나누는 연산 혹은 2로 나누는 연산 혹은 -1 연산을 더하는 것)

그렇게 DP테이블이 완성되었다면 N값을 프린트한다.