문제: 1로 만들기
이 문제는 두 번째로 풀어보는 문제다. 처음 풀 때는 dp의 개념을 제대로 이해하지 못해서 어려웠는데, 두 번째는 훨씬 수월했다.
문제와 입력, 출력은 위에 링크를 통해 확인할 수 있다.
n=int(input())
dp=[0]*(n+1)
for i in range(2,n+1):
dp[i]=dp[i-1]+1 #1을 빼는 방법을 사용했을 때
if i%2==0:
dp[i]=min(dp[i],dp[i//2]+1) #2로 나눴을 때와 비교
if i%3==0:
dp[i]=min(dp[i],dp[i//3]+1) #3으로 나눴을 때와 비교
print(dp[n])
이 문제의 연산하는 방법은 총 세가지이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
그리고 문제에서 원하는 답은 1을 만드는데 필요한 연산 횟수의 최솟값이기 때문에 1을 빼는 것보다 2와 3으로 나누는 것을 우선순위로 두었다.
2와 3으로 모두 나누어 떨어지는 숫자가 있기 때문에 모든 경우의 수를 비교했다.
dp는 거꾸로 생각하는 방식이다. 처음에 이 문제를 보면 주어진 숫자에서 어떻게 줄어들까를 생각하지만 dp를 사용하면 1부터 거슬러 올라가서 주어진 숫자에 도달한다. 다양한 방향에서 생각하는 방식을 익혀야겠다.
