[백준] 1로 만들기

백준의 해당 문제는 링크를 통해 들어가서 풀어볼 수 있다.

 

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

 

문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10의 6승 보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

정답

N = int(input())

dp = [0] * 10000001

#dp[i] : 숫자 i를 만드는데 필요한 최소 연산 횟수
#보텀업
for i in range (2, N+1) :
    dp[i] = dp[i-1] + 1 # 1을 빼주는 경우는 모든 숫자에 대해서 가능
    
    if i % 2 == 0: # 2로 나누어 떨어지는 경우, 최소값 갱신
        dp[i] = min(dp[i], dp[i//2] + 1) 
    
    if i % 3 == 0 :# 3으로 나누어 떨어지는 경우, 최소값 갱신
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[N])

 

공부한 내용

 

먼저, 저번 포스팅에서 DP 문제를 시작했다고 했다. 이번 문제를 풀면서 백준의 DP 문제에 대해서 조금 알게 되었는데 아래의 포스팅을 참고하면 DP 문제들의 유형에 대해서 잘 알 수 있다.

 

https://ppusda.tistory.com/101

동적계획법 (Dynamic Programming; DP) (with. 백준 1912)

 

그래서, 이번 문제는 각 연산들의 사용하는 횟수 중에서 최솟값을 구하는 것이 이 문제의 킥이다 !

그러기 위해서 먼저, dp라는 객체를 생성해서 최종적인 숫자 1을 만드는데 필요한 최소 연산 횟수 array를 만들어준다. 여기에 이제 입력값 N에 대해서 누적되는 연산 횟수를 저장해주는 것이다.

 

먼저, for 반복문을 통해서 2(최솟값) ~ N(코드에서는 N+1)까지 i가 반복되게 만들어주고,

dp[i] = dp[i-1] + 1 을 통해서 1을 빼주는 경우를 거친 다음, i값이 2로 나뉘어지는 경우와 3으로 나뉘어지는 경우를 나누어서 각각 min()을 통해 앞서 계산해준 dp[i]와 비교해서 최솟값을 저장해준다.

 

어디에 ? 숫자 1을 만드는게 필요한 최소 연산 횟수 array인 dp에 !!

 

그리고 마지막으로 입력한 N의 위치를 dp에서 찾아주면, 최소 연산횟수가 출력된다.

 

정리해보면, 아래의 코드를 작성해줄 수 있는지 없는지가 이 문제를 푸는데에 가장 중요한 핵심이 된다.

 

1을 빼주는 경우 : dp[i] = dp[i-1] + 1

 

2를 나누어주는 경우 : dp[i] = dp[i//2] + 1

 

3을 나누어주는 경우 : dp[i] = dp[i//3] + 1