[알고리즘] #03 다이나믹 프로그래밍-1로 만들기

🛠 '1로 만들기' 문제

🔧  문제 

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

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

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

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

4. X에서 1을 뺀다.

 

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

 

- 입력조건 : 첫째 줄에 정수 X가 주어진다. (1 <= X <= 30,000)

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

 

입력예시	출력예시
26	3

---

🔧 아이디어

다이나믹 프로그래밍의 조건은 다음과 같다.

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

이 문제는 두 조건 모두 만족하므로 다이나믹 프로그래밍 bottom-up 방법을 통해 구현해보고자 한다.

 

1) 1의 경우

- 1은 더 이상 처리를 하지 않아도 된다. 따라서 f(1) = 0

 

2) 2의 경우(2의 배수)

- 2로 나누어떨어지므로 가능한 연산은 '2로 나누기', '1 빼기'이다.

a. 2로 나눌 경우 : f(2) = (2로 나눔) + f(1) = 1 + f(i//2) = 1번 연산

b. 1을 뺄 경우 : f(2) = (1 뺌) + f(1) = 1번 연산

- 두 값이 같으므로 최솟값 생각할 필요 없이 f(2) = 1

 

3) 3의 경우(3의 배수)

- 3으로 나누어떨어지므로 가능한 연산은 '3으로 나누기', '1 빼기'이다.

a. 3로 나눌 경우 : f(3) = (3으로 나눔) + f(1) = 1 + f(i//3) = 1번 연산

b. 1을 뺄 경우 : f(3) = (1 뺌) + f(2) = 2번 연산

- 두 값이 다르므로 min(a경우, b경우) = a경우 이므로 f(3) = 1

 

4) 4의 경우

- 2로 나누어떨어지므로 가능한 연산은 '2로 나누기', '1 빼기'이다.

a. 2로 나눌 경우 : f(4) = (2로 나눔) + f(2) = 2번 연산

b. 1을 뺄 경우 : f(4) = (1 뺌) + f(3) = 2번 연산

- 두 값이 같으므로 최솟값 생각할 필요 없이 f(4) = 2

 

5) 5의 경우(5의 배수)

- 생략

-  f(5) = 1 + f(i//5) = 2

 

6) 6의 경우(2와 3의 배수)

- 2, 3으로 나눠지므로 가능한 연산은 '2로 나누기', '3으로 나누기', '1 빼기'

a. 2로 나눌 경우 : f(6) = (2로 나눔) + f(3) = 2

b. 3으로 나눌 경우 : f(6) =(3으로 나눔) + f(2) = 3

c. 1을 뺄 경우 : f(6) = (1 뺌) + f(5) = 2

- min(f(i//2)+1, f(i//3)+1, f(i-1)+1)

- 최솟값은 f(6) = 2

 

7) 7의 경우

- 가능한 연산은 '1 빼기'

a. 1을 뺄 경우 : f(7) = (1 뺌) + f(6) = 1 + f(i-1) =3

- f(7) = 3

 

이런식으로 로직을 생각했다.

 

각 원소를 0으로 할당한 리스트를 만들고 for 문을 돌려 목표값 까지 값을 계산한 후에

연산 횟수의 최솟값을 출력한다.

---

🔧 코드 작성

x = int(input())

answer = [0 for i in range(3002)]

for i in range(2, x+1):
    answer[i] = answer[i-1]+1
    if (i % 2 == 0 ) : # 2의 배수라면
        answer[i] = min(answer[i], answer[i//2] + 1)
    if (i % 3 == 0):  # 3의 배수라면
        answer[i] = min(answer[i], answer[i // 3] + 1)
    if (i % 5 == 0 ) : # 5의 배수라면
        answer[i] = min(answer[i], answer[i//5] + 1)

print(answer[x])

 

https://github.com/Soo-minJeon/CodingTestPractice/blob/ca77e81f3c17dc1cd93b68fa47b8d4355e8eb89b/study_book/ch08_DynamicProgramming/make1.py

 

☺️쥔장깃헙 주소

> https://github.com/Soo-minJeon

Soo-minJeon - Overview