[DP] 백준 1463 1로 만들기

문제링크 www.acmicpc.net/problem/1463

 

처음 풀어본 DP 문제이다. Bottom-up 방식으로 풀었는데 해당 방식이 함수를 재귀호출하지 않아 시간과 메모리를 줄일 수 있다고 한다

 

 

[답코드]

import sys
input=sys.stdin.readline
 
n=int(input())
 
dp=[0 for _ in range(n+1)]
 
for i in range(2, n+1):
    dp[i]=dp[i-1]+1
    if i%3==0 and dp[i]>dp[i//3]+1:
        dp[i]= dp[i//3]+1
    if i%2==0  and dp[i]>dp[i//2]+1:
        dp[i]= dp[i // 2] + 1
 
print(dp[-1])

DP 문제를 처음 접하는 사람은 이해하기 난해한 것 같아 풀이를 자세히 적어보려고 한다

 

 

[풀이법]

① 배열 초기화

입력받은 수 +1의 크기만큼 dp 배열을 만들고 0으로 초기화한다

 

예를 들어 입력받은 수가 5면 길이 6만큼의 배열을 만든다

인덱스(=우리가 연산하고자 하는 수)

이제 배열에는 인덱스 수를 만들기 위해 연산을 사용하는 횟수의 최솟값을 담을 것이다

 

 

② 바로 전 인덱스 값의 +1

 

여기서 사용되는 가장 기본적인 연산은 1을 더해 다음 수를 만들 수 있다는 것이다

그러므로 인덱스 0과 1을 제외하고 직전 인덱스의 값+1을 해준다

 

 

③ 2나 3으로 나누어지는 값은 if 처리

2는 2->1 이므로 연산이 한 번 들어가는 것이 맞다.

하지만 3은 3->1 이 되므로 1이,  4는 4->2->1 2가, 5는 5->4->2->1 이므로 3이 들어가는 것이 맞다

이 처리를 해주기 위해 우리가 전에 배열에 저장해놓은 값을 가져와야 되는데 이것이 '메모이제이션(memoization)' 이다.

 

3을 예로 들어보자

3는 3->1 이므로 1을 만들기 위한 연산횟수+1을 해주는 것이다

4는 4->2->1 이므로 1을 만들기 위한 연산회수+1을 해 2에 넣어주고 2를 만들기 위한 연산횟수+1을 해 4에 넣어주면 된다

 

적용 전

 

적용 후

3의 경우 적용 전에는 2번의 연산을 하면 1이 된다고 했지만 3->1 이므로 아니다

그러므로 만약 계산하고자 하는 숫자가 3으로 나누어지고 현재값이 dp[i//3]+1보다 크다면 값을 바꿔준다

 

④ 값 출력

지금까지 값을 누적해왔다 5의 경우 4를 만들기 위한 연산횟수+1을, 4의 경우 2를 만들기 위한 연산횟수+1 ...

이 배열 중 가장 끝 값을 출력하면 된다

 

 

학부 알고리즘 수업 기말고사에 인덱스 활용하는 문제가 나왔었는데 많은 친구들이 못풀었던 게 기억난다. 

문과 출신이라 수식만 보고 이해하는데는 무리가 있어 좀 자세히 적어봤는데 설명이 어려운 것 같아 틈나는 대로 수정하고 싶다

처음 DP 문제를 접하시는 분들께 도움이 되는 포스팅이 됐으면 좋겠다