1로 만들기

문제

 

 

 

입력

• 첫째 줄에 정수 X가 주어진다. (1 <=X <= 30000)

 

출력

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

 

입력 예시

26

출력 예시

3

풀이 방법

어캐 풀었니

내 코드

a=int(input())

d = [0 for _ in range(a+1)]

for i in range(2,a+1):
    d[i]= d[i-1]+1
    
    if i%5==0 and d[i]> d[i//5]+1:
        d[i]=d[i//5]+1
        
    if i%5==0 and d[i]> d[i//3]+1:
        d[i]=d[i//3]+1
        
    if i%5==0 and d[i]> d[i//2]+1:
        d[i]=d[i//2]+1
        
print(d[a])

Solution

# 정수 X를 입력 받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1000001

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

느낀 점

나는 그냥 값을 비교해서 코드가 돌아가게 작성하였는데

솔루션을 보니 min 함수를 사용하면 더 보기 편하다는 것을 알았다.

 

처음에는 if else문을 사용하였는데 이렇게 풀면 코드가 모든 부분을 보지 않는다는 것을 알고 if문만 사용해 코드를 작성하였다.