📝 BOJ - 1로 만들기

문제

BOJ 1463번 : 1로 만들기

접근 방법

정수 $N$이 주어질 때 이 $N$에 다음의 연산을 가지고 $1$을 만드려고 할 때 연산을 사용하는 횟수의 최소값을 구하는 문제이다.

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

설명

현재에 집중해 숫자 $6$을 가지고 생각해보자! $6$을 만들기 위해서는 $2$에 3을 곱하거나, $3$에 2를 곱하거나, $5$에 1을 더해야한다. 이제 $2$를 만들기 위해서는 $1$에 2를 곱하거나 1을 더해야한다. $3$은 $1$에 3을 곱해 만들 수 있다. $5$는 $4$에 1을 더해서 만들 수 있다.

위의 과정을 살펴보면 결국 어떤 숫자 $N$을 만들기 위해서는 그 전의 숫자를 가지고 연산을 해야 한다. 즉, $N-1$에 1을 더하거나, $N/2$에 2를 곱하거나, $N/3$에 3을 곱해야한다. 그 전의 숫자에서의 연산의 합에 1을 더하여 3가지의 각각 다른 연산 횟수를 구할 수 있는데 그 중 최소값이 연산 횟수의 최소값이다.

결론

1부터 시작해 어떤 수 $i$에 도달하기 위해서는 다음의 연산 중 하나를 해야 한다.

• $i-1$에 1을 더한다.
• $i$가 2로 나누어떨어지는 경우, $i/2$에 2를 곱한다.
• $i$가 3으로 나누어떨어지는 경우, $i/3$에 3을 곱한다.

각 숫자의 연산하기 전의 숫자의 연산 횟수에 1을 더해서 3개의 연산 중 가장 적은 개수의 연산을 현재 숫자의 연산 횟수로 갱신하면 된다. 이를 점화식으로 나타내면 다음과 같다. 이 때 $sum[i]$는 숫자 $i$에 오기까지의 최소 연산횟수이다.

교훈

처음에 $1$부터가 아닌 $N$부터 시작했다. 예를 들면 문제 예시에서 3이 되기 위해서는 4에서 1을 빼거나 6을 2로 나누거나 9를 3으로 나누거나 하면 된다. 할 수 있을 것 같긴한데 복잡해져서 포기했다ㅠㅠ

결국 Newmoon님의 풀이를 참고했는데 1부터 시작하는 것을 보았다. 사실 1에서 시작하든 $N$에서 시작하든 똑같기 때문에 어느 걸 해도 상관없다. 동적계획법에서 항상 현재만 생각했는데 이제는 시작점도 고려해야겠다.

소스 코드

n = int(input())
table = [0] * (n+1)

for i in range(2, n+1):
  table[i] = table[i-1]+1

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

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

print(table[-1])