[백준 / python] 1463번 1로 만들기

오늘은 DP(다이나믹 프로그래밍) 유형인 백준 1463번 문제, 1로 만들기를 풀어보겠습니다!

 

< 문제 확인 >

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

---

📌 문제 탐색하기 

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

문제의 목표는 주어진 정수 N을 1로 만들기 위해 최소 몇 번의 연산이 필요한지 구하는 것입니다.

 

정수 N을 1로 만드는 과정을 거쳐야하며, 가능한 연산은 총 세 가지입니다

<<< 3으로 나누기, 2로 나누기, 1 빼기 >>>

 

계산 횟수를 최대한 줄이기 위해서는 이전 숫자들의 최소 연산을 저장하여 더 큰 숫자에서도

활용할 수 있을 것 입니다! 따라서, DP(다이나믹 프로그래밍) 알고리즘을 사용하면 될 것 같습니다 :)

 

즉, 큰 문제(N에서 1로 만들기)는 작은 문제들(ex. N-1에서 1로 만들기, N-2에서 1로 만들기)의

결과를 사용하여 빠르게 해결할 수 있습니다. 작은 문제들은 N의 값에 따라 중복되며,

이를 DP 테이블에 저장함으로써 반복 계산을 피할 수 있습니다.

 

최소 연산을 위한 테이블을 0으로 초기화 후, 각 숫자에 대해 기본적으로 dp[n-1] + 1을 고려해봅니다.

추가로, n이 2로 나누어 떨어진다면 dp[n//2] + 1을, 3으로 나누어 떨어진다면

dp[n//3] + 1을 고려하여 최소 연산 횟수를 선택합니다.

 

dp[n] = dp[n-1] + 1을 가장 처음으로 시도하지만 이후 min을 활용하여

다시 연산 횟수를 비교하여 재설정 되므로 문제는 없습니다!

 

즉, dp[n] = min(dp[n], dp[n//2] + 1) or min(dp[n], dp[n//3] + 1)을 활용하여

N을 1로 만드는 최소 연산 횟수를 알아낼 수 있습니다!

 

✔️ 가능한 시간복잡도

N은 최대 10^6이고 N에 대해 최소 연산 횟수를 계산해야 하므로,

이 문제는 O(N)의 시간복잡도로 해결할 수 있습니다.

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 자연수 N을 입력 받습니다.

2. DP을 테이블 초기화 합니다.

3. 각 숫자에 대한 최소 연산 횟수를 계산하여 저장합니다.

(효율적으로, dp[n] = min(dp[n], dp[n//2] + 1) or min(dp[n], dp[n//3] + 1)식을 사용합니다.)

4. 저장된 DP 테이블에서 입력받은 N에 대한 값을 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

무문 별하게 “맞았습니다”가 나올 때까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

런타임 에러가 발생한 이유는 N의 값과 DP 테이블의 크기가 맞지 않기 때문입니다.

# DP 테이블 초기화 및 채우기
dp = [0] * N

위 코드처럼 DP 테이블을 초기화 할 때, N개로 설정하였는데

N까지의 값을 저장할 수 있도록 크기를 N+1로 설정해야 했습니다.

---

📌 정답 코드

# 자연수 N 입력
N = int(input())

# DP 테이블 초기화 및 채우기
dp = [0] * (N + 1)

for n in range(2, N + 1):
    # 우선 dp[i-1] + 1로 지정
    dp[n] = dp[n-1] + 1
    
    # 2로 나누어 떨어질 경우
    if (n % 2 == 0): dp[n] = min(dp[n], dp[n//2] + 1)
    
    # 3으로 나누어 떨어질 경우
    if (n % 3 == 0): dp[n] = min(dp[n], dp[n//3] + 1)

print(dp[N])

다이나믹 프로그래밍 알고리즘을 통해 여러가지 문제를 풀어보았습니다!

코딩테스트에서 자주 볼 수 있는 알고리즘을 열심히 학습할 수 있어서

아주 의미있는 시간이 되었습니다! 4기 활동에도 꼭 참여할 것 입니다 ㅎㅎ

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no