[DP] 이코테 “1로 만들기” Python 풀이

문제

• 정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
  • 1) X가 5로 나누어떨어지면, 5로 나눈다.
  • 2) X가 3으로 나누어 떨어지면, 3으로 나눈다.
  • 3) X가 2로 나누어 떨어지면, 2로 나눈다.
  • 4) X에서 1을 뺀다.
• 정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들려고 한다.
• 연산을 사용하는 횟수의 최솟값을 출력하시오.
• 예를 들어, 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
  • 26 - 1 = 25
  • 25 / 5 = 5
  • 5 / 5 = 1

입력 조건

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

출력 조건

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

입력 예시

26

출력 예시

3

풀이

• 각각의 값을 만들 수 있는 최소 연산 횟수를 바텀업 방식으로 구해나가면 됩니다.
• dp_table[1] 은 1의 최소 연산 횟수이므로, 0 입니다.
• dp_table[2] 는 2의 최소 연산 횟수이므로, 1 입니다.
• 따라서, 2부터 채워나가면 됩니다.

예제 코드

import sys

# 정수 X를 입력받기
x = int(sys.stdin.readline().rstrip())

# DP 테이블 생성
dp_table = [0] * 30001

# 바텀업 진행
for i in range(2, x+1):

    # 현재 값에서 -1 을 했을 때가 최소 연산 횟수라고 가정하고, 
    # 해당 값에서 +1 함으로써, 현재 값까지의 최소 연산 횟수를 default로 지정
    dp_table[i] = dp_table[i-1] + 1
    # 현재 값을 5로 나눴을 때의 연산 횟수와 현재 값을 -1로 뺐을 때의 연산 횟수 중, 최솟값을 최소 연산 횟수로 지정
    if (dp_table[i] % 5 == 0):
        dp_table[i] = min(dp_table[i], dp_table[i // 5] + 1)
    # 현재 값을 3으로 나눴을 때의 연산 횟수와 현재 값을 -1로 뺐을 때의 연산 횟수 중, 최솟값을 최소 연산 횟수로 지정
    if (dp_table[i] % 3 == 0):
        dp_table[i] = min(dp_table[i], dp_table[i // 3] + 1)
    # 현재 값을 2로 나눴을 때의 연산 횟수와 현재 값을 -1로 뺐을 때의 연산 횟수 중, 최솟값을 최소 연산 횟수로 지정
    if (dp_table[i] % 2 == 0):
        dp_table[i] = min(dp_table[i], dp_table[i // 2] + 1)

print(dp_table[x])

참고

• 이것이 취업을 위한 코딩 테스트다. with python