https://www.acmicpc.net/problem/1463
1463번: 1로 만들기첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.www.acmicpc.net
처음 구현해본 dp라 처음에는 헤멨는데
원리만 알고 나니깐 너무 간단하다.
상향식 접근?
처음부터 1씩 더해가며 각각의 값을 업데이트하면 된다.
사실 2,3을 업데이트할 필요도 없음
x=int(input())cnt_list=[-1]+[0]+[1]+[1]*(x-1) ##첫번째는 안쓸거니깐 x+1개의 리스트 만들기
for i in range(3,len(cnt_list)): ###0,1,2,3을 제외하고 dp
cnt=cnt_list[i-1]+1 #1을 빼서 바로 전 수로 만드는 경우 if i%3==0:
cnt=min(cnt,cnt_list[i//3]+1)
## 3으로 나누었을때의 경우의 수는, 이를 3으로 나눴을때의 경우의 수 +1 if i%2==0:
cnt=min(cnt,cnt_list[i//2]+1) ##위와 동 ##최솟값만 남기고
cnt_list[i]=cnt #최솟값 업데이트print(cnt_list[x])