[파이썬] 백준 1463 : 1로 만들기

[파이썬] 백준 1463 : 1로 만들기

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

1463번: 1로 만들기

실버 3

DP

---

접근

1로 빼거나

2로 나누어지면 2로 나누거나

3으로 나누어지면 3으로 나눈다.

 

이걸 그대로 구현하면 10을 입력값으로 주었을 때 예외가 생긴다.

위의 방법을 그냥 분기로 구현하면 10 > 5 > 4 > 2 > 1  이렇게 총 4번이 되지만,

10 > 9 > 3 > 1로 총 3번이면 1로 만들 수 있는 방법이 있기 때문이다.

 

만약 입력 값에서 처음의 3가지 경우를 각각 사용했을 때 구해진 연산 횟수중에 가장 작은 값을 선택할 수 있다면 좋을 것이다.

 

 

문제를 상향식으로 푼다고 가정하면 10을 예시로 했을 때 다음과 같은 정리가 가능하다.

(dp라는 이름의 리스트를 선언하고 각각의 인덱스 값은 해당 값을 1로 만드는 최소 연산 횟수를 저장하도록 한다. 그리고 필요한 값은 dp리스트 내에서 참조하도록 한다.)

 

10은 1로 빼거나 2로 나눌 수 있는 선택지가 있다.

 

1. 10에서 1을 빼면 9가 된다. 여기서 9가 1이 되는 최소 횟수를 알고 있다면,

(10에서 9를 만든 연산 횟수 : 1) + (9에서 1을 만든 최소 연산 횟수)가 10에 대한 연산 값이 된다.

dp[n] = 1+dp[n-1]

 

2. 10에서 2를 나누면 5가 된다.

여기서 5가 1이 되는 최소 횟수를 알고 있다면,

(10에서 5로 만든 연산 횟수 : 1) + (5에서 1을 만든 최소 연산 횟수)가 10에 대한 연산 값이 된다.

dp[n] = 1+dp[n//2]

 

이 두가지 경우를 비교했을 때 가장 작은 값이 10에서 1을 만드는 최소 연산 횟수가 될 것이다.

 

같은 방법으로 입력 값이 6일 때를 살펴보자.

6은 1로 빼거나 2로 나누거나 3으로 나누는 선택지가 있다.

 

1. 6에서 1을 빼면 5가 된다.

(6에서 5를 만든 연산 횟수 : 1) + (5에서 1을 만든 최소 연산 횟수)

dp[n] = 1+dp[n-1]

 

2. 6에서 2를 나누면 3이 된다.

(6에서 3을 만든 연산 횟수 : 1) + (3에서 1로 만든 최소 연산 횟수)

dp[n] = 1+dp[n//2]

 

3. 6에서 3을 나누면 2가 된다.

(6에서 2를 만든 연산 횟수 : 1) + (2에서 1로 만든 최소 연산 횟수)

dp[n] = 1 + dp[n//3]

 

따라서 이 세가지 경우를 비교했을 때 가장 작은 값이 6을 1로 만드는 최소 연산 횟수가 될 것이다.

 

결국 모든 경우의 수는 다음과 같은 점화식으로 정리할 수 있다.

 

dp[n] = min(dp[n-1], dp[n//2], dp[n//3]) + 1

 

이때 입력한 n은 2의 배수나 3의 배수가 아닐 수도 있는 경우가 존재하므로, 가장 먼저 1을 뺀 경우를 리스트에 저장한 후 그 값이 2의 배수인지 3의 배수인지에 따라 경우의 수를 비교해야 한다.

 

코드

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

dp = [0] * (n+1)
for i in range(2, n+1):
    dp[i] = dp[i-1] + 1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
print(dp[n])

 

n이 1인경우 최소 연산 횟수는 0이다.