다이나믹 프로그래밍 정복기 2 - 연습문제 1로 만들기 -

1. 문제

 

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

1463번: 1로 만들기

 

1이상의 정수 x가 주어질때, 

 

1) x가 3으로 나누어 떨어지면 3으로 나눈다

2) x가 2로 나누어 떨어지면 2로 나눈다

3) x에서 1을 뺀다

 

3가지 연산을 적절히 사용해서 1을 만들고 싶다

 

연산을 사용한 횟수의 최솟값을 출력한다면?

 

 

2. 나의 풀이

 

다이나믹 프로그래밍 연습문제니까 다이나믹 프로그래밍을 써야겠지

 

기본이 바텀업이고 반복문 구현이라고 배웠으니까 이에 따라보자

 

작은 문제부터 구해놓고, 이들을 이용해서 반복문을 구현한다면..

 

1이상이니까 dp[0] = 0, 1은 연산을 안해도 1이니까 dp[1] = 0

 

2는 1을 빼거나 2로 나누면 1번만에 1이 되니까 dp[2] = 1

 

3은 1을 빼고 2로 나누거나, 3으로 1번만 나누거나.. dp[3] = 1

 

그러면 4부터는?

 

4에서 1을 빼면 3이고, 3을 1로 만드는 방법은 dp[3]에 있다.

 

5에서 1을 빼면 4이고 4를 1로 만드는 방법은 dp[4]에 있다.

 

6에서 1을 빼면 5이고 5을 1로 만드는 방법은 dp[5]에 있다.

 

....

 

n에서 1을 빼면 n-1이고 n-1을 1로 만드는 방법은 dp[n-1]에 있다

 

#################################

 

근데 4에서 2로 나누면 2이고, 2를 1로 만드는 방법이 dp[2]

 

6같은 경우도 2로 나누면 3이고 3을 1로 만드는 방법이 dp[3]

 

혹은 3으로 나누면 2이고 2를 1로 만드는 방법이 dp[2]

 

#############

 

그러면 결국 dp[n]은 연산을 1번 수행하고, dp[n-1]과 더하거나, 

 

n이 2로 나눌 수 있다면 dp[n//2]와 1을 더하거나

 

n이 3으로 나눌 수 있다면 dp[n//3]과 1을 더하거나..

 

3가지 경우가 가능하다

 

연산의 최솟값을 구해야하므로 n마다 가능한 경우를 비교해서 최솟값을 dp[n]에 저장하면 될 것

 

from sys import stdin

dp = [0]*((10**6)+1)

dp[1] = 0

dp[2] = 1

dp[3] = 1

N = int(stdin.readline())

for n in range(4,N+1):
    
    if n % 3 == 0 and n % 2 == 0:
        
        dp[n] = min(dp[n//3],dp[n//2],dp[n-1]) + 1
    
    elif n % 3 == 0:
        
        dp[n] = min(dp[n//3],dp[n-1]) + 1
    
    elif n % 2 == 0 :
        
        dp[n] = min(dp[n//2],dp[n-1]) + 1
    
    else:
        
        dp[n] = 1 + dp[n-1]

print(dp[N])

 

10^6까지가 최댓값이므로 배열을 10^6 + 1까지 초기화하고

 

1,2,3은 각각 기본으로 구한 다음에 4부터 N까지 반복문을 돌아서 dp를 채워나간다

 

각각의 n이 2로 나누어 떨어지고 3으로도 나누어 떨어지는 경우

 

2로만 나누어 떨어지는 경우

 

3으로만 나누어 떨어지는 경우

 

모두 나누어 떨어지지 않아서 1 빼기만 가능한 경우

 

4가지가 있고

 

각각에서 최솟값을 dp[n]에 저장해가면 끝

 

from sys import stdin

dp = [0]*((10**6)+1)

dp[1] = 0

dp[2] = 1

dp[3] = 1

N = int(stdin.readline())

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

 

혹은 뭐 조금 더 간단하게?

 

1을 빼는건 모든 n이 가능하므로 일단 dp[n] = 1 + dp[n-1]에 저장해놓고

 

if문만 사용해서 만약에 n이 3으로 나누어 떨어진다면..?

 

이미 1을 뺀 연산을 저장한 dp[n]과 3으로 나눈 dp[n//3]과 1을 더한걸 비교해서 최솟값으로 갱신

 

근데 여기에 2로도 나누어 떨어진다면??

 

1을 뺀 연산, 3으로 나눈 연산 중 비교해서 최솟값을 갱신한 dp[n]과 2로 나누어서 dp[n//2]와 1을 더한 연산 중 최솟값을 재갱신

 

근데 뭐 3으로 안되고 2로만 나눌 수 있다면 if n % 2 == 0만 작동하고

 

모두 나눌 수 없다면 1+dp[n-1]만 가능하니까.. 상당히 깔끔

 

 

3. 되돌아보기

 

옛날 같았으면 못풀었을것 같은데 ㅋㅋㅋㅋ

 

교육받아서 그런가 뭔가 상당히 잘 풀었다