백준 1463 - 1로 만들기 (Python)

문제

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

풀이

n = int(input())
memo = [0]*(n+1)
for i in range(2,n+1):
    k=[memo[i-1]]
    if i%3==0:
        k.append(memo[i//3])
    if i%2==0:
        k.append(memo[i//2])
    memo[i] = min(k)+1
print(memo[n])

 

다이나믹 프로그래밍(DP) 문제이다.

연산을 통해 n을 1로 만든다는 생각 보다는

1부터 시작해서 n으로 만든다는 생각으로 풀이하였다.

 

어떤수 n을 만들기 위해 필요한 연산의 가짓 수는 총 3가지를 고려해야한다.

1. n/3를 만드는데 필요한 연산 수 +1 (n이 3으로 나누어 떨어질 때)

2. n/2를 만드는데 필요한 연산 수 +1 (n이 2로 나누어 떨어질 때)

3. n-1을 만드는데 필요한 연산 수 +1

이중 최솟값이 n을 만드는데 필요한 최소 연산의 수가 되는 것이다.

 

memo라는 배열을 만들어두고 memo의 1번째 값을 0으로 둔 후, 2부터 n까지 타뷸레이션 방식을 사용하였다.

(memo의 i번째 위치에 저장된 값은 i를 만들기 위한 최소연산)

 

6을 예시로 들면, 6을 만들기 위한 방법은 2를 3배하거나, 3을 2배하거나, 5에 1 더하는 경우 총 3가지 이므로,

memo[6] = min(memo[2],memo[3],memo[5]) + 1 가 된다.