1 분 소요

부품 찾기

문제

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.

  1. X가 5로 나누어 떨어지면 5로 나눈다.
  2. X가 3으로 나누어 떨어지면 3으로 나눈다.
  3. X가 2로 나누어 떨어지면 2로 나눈다.
  4. X에서 1을 뺀다.

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


입력조건

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


출력조건

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


입력예시

26

출력예시

3


나의 코드

#정수 받기.
n = int(input())

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

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

»input

26

»output

3

🌝 Thinking

문제를 풀다가 도저히 답안 접근법을 참고하여 코드를 완성하였다.

탑다운 방식이랑 바텀업방식은 사실 한끗차이라고 생각하는데, 바텀 업방식은 익숙치가 않은 것 같다.

사실 바텀업 방식이 사람이 생각하는 사고랑 비슷할텐데,,, 사실 그 사고의 흐름에 잘 집중해서 차분하게

구현을하면 더 쉽게 코드를 만들 수 있을 것 같다.

답안 코드

# 위 코드와 상동


💡 깨달은 점.

  1. DP 문제를 잘 풀려면, sequence의 인접한 항들의 관계식을 점화식으로 잘 유도해내야 하는 것 같다.

출처

이것이 코딩 테스트다 - 나동빈 저

댓글남기기

참고