Solved.ac Class [3]

실버 4 등급 : 1 만들기

문제 설명

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

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

예제 입출력

input
10

output
3

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

문제 접근 방식

처음에는 그리디 알고리즘 처럼 브루트포스와 같이 풀려고 했지만 계속 반례가 생겨 이런식으로는 풀지 못할 것을 깨달았습니다. 이 문제는 다이나믹 프로그래밍을 통해서 풀 수 있습니다. 다이나믹 프로그래밍이란 문제를 더 작은 단위로 쪼개어 해결하는 알고리즘이라고 합니다. 이 작은 단위의 문제들이 반복해서 일어나기 때문에 값을 저장해 놓는 식으로 해결합니다. 그래서 조건이 있습니다.

  1. 부분 문제들이 겹치는가 (반복되는가) ex ) 피보나치 수 : N번째 항(큰 문제) = N-1번째 항(작은 문제) + N-2 번째 항(작은 문제)
  2. 최적 부분 구조 (문제의 정답을 작은 문제의 정답으로부터 구할 수 있는가) ex ) 최단경로 구하기 : A에서 C로 가는 최단경로 (큰 문제) = A에서 B로가는 최단경로(작은 문제) + B에서 C로가는 최단경로(작은 문제)
  • Top - down : 위에서 아래로 해결한다. (ex : 재귀함수)

문제를 쪼갠다. 작은 문제를 푼다. 작은 문제의 정답으로 큰 문제를 해결한다.

  • bottom - up : 아래에서 위로 (ex : 반복문)

작은 문제부터 풀어나간다. 문제의 크기를 점점 크게 만들어 푼다. 작은 문제들을 해결했기 때문에, 한단계 위의 큰 문제를 풀 수 있다. 최종적인 문제를 해결한다.

  • 문제를 해결할때

점화식을 정의한다. 문제를 어떠한식으로 쪼갤지 (작게 만들지) 생각한다. 작은 문제의 답을 통해 어떻게 최종적인 문제를 해결할 수 있을지 생각한다.

그래서 이번 문제의 점화식은 아래와 같습니다. dp(N) = min ( dp(N//3) +1, dp(N//2)+1 , dp(N-1)+1 ) 3가지 중에 가장 작은 값을 가져가야 합니다.

문제 풀이

import sys
n = int(sys.stdin.readline())

memo = [0] * (n+1)

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

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

print(memo[n])

일단 memorization을 위해 리스트를 n+1개 만큼 만들어줍니다. (n=9라고 가정하겠습니다)
계산하기 편하게 d[1]을 1번째 인 것 처럼 만들어준다.

1을 빼고 시작하는 이유는 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되기 때문이다. +1해주는 이유는 memo는 결과가 아닌 계산한 횟수를 저장하는 것 이기 때문이다.
memo[i]에는 더하지 않는 이유는 memo[i]가 1을 더해준 이력이 있기 때문이다.

memo[9]는 2로 나누어 지지 않기 때문에 min(memo[9-1]+1, memo[9//3]+1)식에 의해 나온다.
위 식대로 memo[2]부터 구하게 됩니다.
memo[1]= 0
memo[2]= (memo[2-1=1]+1==1 , memo[2//2=1]+1 == 1 )
memo[3]= (memo[3-1=2]+1==2 , memo[3//3=1]+1 == 1 ) =1
memo[4]= (memo[4-1=3]+1==2 , memo[4//2=2]+1 == 2 ) =2
memo[5]= (memo[5-1=4]+1) =3
`
`
이렇게 계산된 값을 활용해서 계속 구해줍니다.
`
`
memo[9]= (memo[9-1=8]+1 ==4, memo[9//3==3]+1 ==2) =2

출처: https://infinitt.tistory.com/246