[CodingTest] 1로 만들기 ( DP )

문제

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

1) X가 5로 나누어떨어지면, 5로 나눈다.

2) X가 3으로 나누어 떨어지면, 3으로 나눈다.

3) X가 2로 나누어 떨어지면, 2로 나눈다.

4) X에서 1을 뺀다.

 

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

X = 26일 경우
1. 26 - 1 = 25
2. 25 /5 = 5
3. 5 / 5 = 1

입력

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

출력

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

입력 예시

26

출력 예시

3

 

알고리즘 

정수X가 주어지면 연산 4개를 사용하여 1로 만들어야 한다. 1이 되는 경우는 여러가지이고 연산횟수도 다양하다. 

 

 

 

 

 

연산횟수의 최솟값을 구하는 것이 문제이다. 최솟값을 구하려면 모든 경우를 '탐색'해야한다. 그리고 '비교'하고 '저장'해야한다. 

 

1) 탐색

완전탐색에는 두 가지 방법이 있다. 

 

- 반복문 (Bottom-Up)

- 재귀호출 (Top-Down)

 

재귀호출방식의 경우, 정수X가 커질수록 호출되는 메소드 또한 많아진다.  그러므로 메모리 관리를 위해 반복문 사용을 추천한다.

 

2) 비교

최솟값을 구하기 위해, min 함수를 이용한다.  

 

 

 

 

 

Top-Down 방식으로 설명하면, 26이 되려면 4가지 경우가 있다. 4가지 경우 중 최소 연산횟수에 +1 한 값이 26의 연산횟수가 된다. ÷5, ÷3, ÷2, -1 의 연산횟수 중 최솟값에 +1을 하여 26의 연산횟수를 구한다.

 

3) 저장

정수X는 1<=X<=30,000이 므로 30000개의 방이 있는 리스트를 생성한다. 그리고 1)탐색과 2)비교를 하여, X의 최솟값을 넣는다. 26은 13과 25의 값중 최솟값의 +1이 26의 연산횟수가 된다. 

 

 

풀이

- Bottom-Up 방식

n = int(input())
d = [0]*30001 #최솟값 저장을 위한 배열 생성

#Bottom-up 방식
for i in range(2,n+1) : #반복문으로 2부터 n까지 연산횟수 최솟값 계산하기
 
  d[i] = d[i-1] + 1 # -1의 경우 ( 일단 삽입해놓기 )
  if i % 5 == 0 : # ÷5의 경우
    d[i] = min(d[i], d[i//5] + 1) # 최소비교
  if i % 3 == 0 : # ÷3의 경우
    d[i] = min(d[i], d[i//3] + 1) # 최소비교
  if i % 2 == 0 : # ÷2의 경우
    d[i] = min(d[i], d[i//2] + 1) # 최소비교

print(d[n]) # n의 연산횟수 최솟값 출력하기

 

-Top-Down 방식

import sys
sys.setrecursionlimit(10**6) #재귀호출 가능 깊이 늘리기

x = int(input())
d = [0]*30001 # 최솟값 저장을 위한 배열 증가시키기

#재귀호출함수
def calculate(x) :
  # 기저조건 
  if x == 1 : return 0

  # 재귀호출
  if x > 1 : 
    d[x] = calculate(x-1)+1 # -1의 경우
  if x % 5 == 0 : 
    d[x] = min(d[x],calculate(x//5)+1) # ÷5의 경우
  if x % 3 == 0 : 
    d[x] = min(d[x],calculate(x//3)+1) # ÷3의 경우
  if x % 2 == 0 : 
    d[x] = min(d[x],calculate(x//2)+1) # ÷2의 경우

  return d[x] #최소값을 return 하기 

print(calculate(x)) #출력

 

 

 

---

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24