백준 알고리즘 | 1463 : 1로 만들기 (Python / 파이썬)

---

1로 만들기 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	121152	40368	25255	32.162%

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

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

3. 1을 뺀다.

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

​

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

​

출력

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

​

알고리즘 분류

다이나믹 프로그래밍

---

 

백준 알고리즘 # 1463번 : 1로 만들기

# 1463번 : 1로 만들기
x = int(input())
# x = 10

result = [0 for _ in range(x + 1)]
# result = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

for i in range(1, x + 1):
    if i == 1:
        result[i] = 0
        continue
    
    result[i] = result[i - 1] + 1

    if i % 3 == 0 and result[i // 3] + 1 < result[i]:
        result[i] = result[i // 3] + 1

    elif i % 2 == 0 and result[i // 2] + 1 < result[i]:
        result[i] = result[i // 2] + 1
    '''
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0] i = 2
    [0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0] i = 3
    [0, 0, 1, 1, 2, 0, 0, 0, 0, 0, 0] i = 4
    [0, 0, 1, 1, 2, 3, 0, 0, 0, 0, 0] i = 5
    [0, 0, 1, 1, 2, 3, 4, 0, 0, 0, 0] i = 6
    [0, 0, 1, 1, 2, 3, 2, 3, 0, 0, 0] i = 7
    [0, 0, 1, 1, 2, 3, 2, 3, 4, 0, 0] i = 8
    [0, 0, 1, 1, 2, 3, 2, 3, 3, 4, 0] i = 9
    [0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3] i = 10
    '''
    
print(result[x])

풀이

먼저 동적 프로그래밍이란 큰 문제를 한 번에 해결하기 힘들 때, 작은 여러 개의 문제로 나누어서 푸는 방법이다.

​

작은 문제들을 풀다보면, 비슷하고 같은 문제들을 반복해서 푸는 경우가 생기는데

이때 이런 문제들을 매번 다시 계산하지 않고, 리스트나 다른 곳에 값을 저장해두었다가

이 값들을 다시 사용하는 기법이 동적 프로그래밍이다.

​

이것을 기억해서 문제 풀이를 시작하면, 처음에 x변수로 정수를 입력받고

result 변수를 만들어서 [] 리스트에 0을 x변수만큼 추가한다.

​

그리고 for문으로 1부터 x + 1까지 반복해주고 if문으로 i가 1일 때

result[1] = 0으로 만들고 i = 2 ~ 10를 반복한다.

​

반복하면서 result[i] = result[i - 1] + 1로 계속해서 리스트의 인자를 초기화시키고

i % 3 == 0, i % 2 == 0으로 3의 배수일 때 2의 배수일 때 해당하는 인자를

3과 2로 나눈 뒤 1씩 더해줘서 다시 초기화시켜서 저장하면

​

x = 10으로 입력받은 수가 3번만에 1이 된다는 것이 출력되면서 끝이난다.

​

사실 다이나믹 프로그래밍 알고리즘으로 풀이한 것은 처음이라 아직 이해가 안가는 부분도 많아서

코드 하나하나를 뜯으면서 공부해봤다..

​

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

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

3. 1을 뺀다.

위 세 가지 조건에 맞춰서 풀이하면 되는 걸로 생각해서 쉽게 접근했지만 결코 쉽지 않았다.

혼자의 힘으로 코드를 짤 수 있을 때까지 다시 풀어봐야할 문제!👏

​

자세한 코드가 궁금하신 분들은 아래 GitHub 참고해주세요🙏

wook2124/Algorithm

최종 소스코드