[백준] 1463번 파이썬 (1로 만들기)

1. 문제와 예제

(문제 링크: https://www.acmicpc.net/problem/1463)

1463번: 1로 만들기

문제

예제

---

2. 전체 코드

# 입력 받기
N = int(input())
d = [0] * 1000001 # DP 테이블 (N 최댓값 10^6)

# 다이나믹 프로그래밍 시작
for i in range(2, N+1):
    d[i] = d[i-1] + 1 # 숫자에서 1을 빼는 케이스
    if (i % 2 == 0): # 숫자가 2로 나누어 떨어지는 경우
        d[i] = min(d[i], d[i//2] + 1) # 숫자에서 2를 나눈 케이스와 비교해서 최솟값 남김
    if (i % 3 == 0): # 숫자가 3으로 나누어 떨어지는 경우
        d[i] = min(d[i], d[i//3] + 1) # 숫자에서 3을 나눈 케이스와 비교해서 최솟값 남김

# 결과 출력하기
print(d[N])

 

---

3. 코드 해설

동적 프로그래밍을 사용하는 문제다. 큰 문제를 작은 문제로 나누어 푸는 알고리즘으로 작은 문제의 결과를 메모리에 저장해두었다가, 같은 작은 문제가 나타날 때마다 이를 활용하여 문제를 푸는 방식이다. 이 문제를 예로 들면, 10->9->3->1 이러한 방식으로 바라보는 게 아니라 1에서 10으로 가려면 어떤 방법이 최소일까로 뒤집어서 생각하는 것이다. 그렇게 하면 작은 숫자가 본인 숫자를 거쳐가는 큰 숫자의 연산 개수를 구하는 데 도움을 줘 빠르게 구할 수 있다.

동적 프로그래밍으로는 O(n^2) -> O(f(n))으로 시간 복잡도를 줄일 수 있다. 자세한 내용을 알아보기 위해서는 아래 게시글도 참고하자.

https://velog.io/@qtly_u/DP-%EB%B0%B1%EC%A4%80-1463%EB%B2%88-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0

 

DP, 백준 1463번(Python) -1로 만들기