[BaekJoon] 1463 1로 만들기

▶ 문제 :

 

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

 

 

▶ 코드 : 

 

num = int(input())

data = {1:0}

i = 2

while True:
    if i == num+1:
        break

    data[i] = data[i-1] + 1
    if i % 3 == 0:
        data[i] = min(data[i], data[i//3] + 1)
    if i % 2 == 0:
        data[i] = min(data[i], data[i//2] + 1)

    i += 1

print(data[num])

 

▶ 문제 풀이 :

 

1. DP 방식을 사용해서 풀이하는 문제이다. 

2. 초기 값 1을 제외한 이후 숫자(2) 부터 반복을 진행한다.

3. 해당 숫자에서 1을 뺀 경우(이 경우는 이전 결과값에 1을 더함) 3으로 나눈 경우 2로 나눈 경우 모두를 비교해가면서 data 해쉬테이블을 채운다. 

4. 원하는 인덱스의 결과를 출력한다.