[알고리즘/동적 계획법] 1463 번 : 1로 만들기 - python

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

1463번: 1로 만들기

 

---

• 문제
• 소요시간:34분 10초

---

• 설계하기(접근방법) 

1. n을 입력받는다.

2. 알고리즘 해석

1) 그리디로 하는 경우와 그 예외 사항

10 5 4 2 1  : 5번

10 9 3 1 : 4번

 

          

다음의 경우와 같이 그리디로 하는 경우(3으로 나누어지면 나눔, 안되면 2로 나눔, 안되면 1을 뺀다)

가장 효율적인 경우의 수가 아니다.

따라서 아래에서부터 수를 저장하는 동적 계획법으로 문제를 해결해야 할 것이다

 

2) 동적 계획법

총 3가지 검증 방법이 있다

1) n이 3으로 나누어지면 dp[n//3]의 값

 

2)n이 2로 나누어지면 dp[n//2]의 값

 

3)n에서 1을 뺀 경우 dp[n-1]의 값

 

이 3가지 값중 작은 값에 +1(검증으로 한 연산)한 값이 dp[n]의 최소값이다

이 검증을 2부터 n+1까지 진행해주면,

2부터 n+1까지 순차적으로 최소값만 dp 리스트에 데이터가 축적된다.

 

ex) 1 ~9까지 이미 연산이 진행된 상황에서 dp[10]의 값을 검증할 떄

1)dp[10//3] = 연산 불가

 

2) dp[10//2] = dp[5] = 3

 

3) dp[10 -1] = dp[9] = 2

 

즉 3)의 값이 최소이기 때문에 dp[10]의 값은 dp[9]+1 = 3이 된다

 

3. dp[n]의 값을 출력한다

 

---

• 코드(출력)

n = int(input())

dp = [0] * (n + 1)

dp[1] = 0


for i in range(2, n + 1):
    val1 = 1e9
    val2 = 1e9
    val3 = 1e9
    if i % 3 == 0:
        val1 = dp[i // 3]
    if i % 2 == 0:
        val2 = dp[i // 2]
    val3 = dp[i - 1]
    dp[i] = min(val1, val2, val3) + 1


print(dp[n])

---

• 얻어갈 부분

1. 동적 계획법과 더 친해졌다.

2. n을 구하기 위해 1부터 n까지 올라가는 방식으로 해결했다.