[ BOJ / 파이썬 ] 1463 1로 만들기

지금 피곤해서 그런지 솔직히 DP 개념이 잘 머리에 안 들어온다.

그래서 DP문제치고 굉장히 쉬운 편에 속하는 해당 개념도 인식이 잘 안 됐다.

 

30분 책상에 엎드려서 자고 왔다.

 

import sys
input = sys.stdin.readline

x = int(input())

dp = [0]*(x+1)
for i in range(2,x+1):
  dp[i] = dp[i-1] + 1
  if i % 3 == 0:
    dp[i] = min(dp[i],dp[i//3] + 1)
  if i % 2 == 0:
    dp[i] = min(dp[i],dp[i//2] + 1)

print(dp[x])

 

다른 분의 코드를 보니 코드 자체는 이해 가는데, 이걸 내가 습득한 개념처럼 안 다가온다.

조금 쉬고 다시 보자.

 

1. 테이블 정의하기

: 어이없게도 리스트 초기화에서 에러가 났다. 아까 피곤해서 자꾸 빈 배열로 초기화를 한 뒤 값을 append가 아닌 = 로 할당하려 해서였다.

테이블은 0을 값으로 가지는 수를 하나 많게 곱해서 초기화

 

2. 재귀식 찾기

: 모든 문제가 그렇겠지만 재귀식을 찾는게 까다로운 문제다. 자칫 잘못하면 n 부터 시작해 값을 빼거나 나눠가며 1까지 단순하게 구할 수 있는데, 친절하게 제시된 두 번째 테스트 케이스에서 그렇게 하면 안 된다는 것을 알 수 있다.

 

: 그래서 초기값을 채워넣은 뒤 나머지를 반복 돌며 채워나간다. 라는 DP의 특성을 다시 잘 생각해본 뒤 풀이하면 조금 더 괜찮다.

 

: 특히 DP:Dynamic Programming:동적계획법은 하향식과 상향식이 있다. 는 3년 전 배운 사실을 다시 상기시키며 계속 문제를 더 많이 접하면 사실 어렵지 않다.

 

: 그래서 해당 문제도 처음 접근했던 상향식이 아닌 하향식으로 풀면 해결이 가능했다.

 

: 혼자 풀어야한다고 다시 접근해보자 . 상향식인지 하향식인지 키워드는 어디서 얻을 수 있을까.

 

:목표값 x에서 최소 연산횟수를 가지며 1) 3으로 나누거나 2) 2로 나누거나 3) 1을 빼야한다. 해당플로우를 bfs로 모두 탐색하지 않는 이상 3가지 경우 중 어떤 것이 최소 연산을 가질 지 미래의 일은 DP를 통해 구하기는 까다롭다. 

반대로 1,2 의 케이스부터 생각해서 다음 수가 3가지 방법 중 어떤 것들이 결합했을 때 연산횟수가 적을 지는 비교하기 쉽다.

그리고 이 때 테이블에 넣을 값이 더 면밀하고 확실하게 정해지는데, 우리가 구하고자 하는 값인 연산횟수를 바로 업데이트하며 올라오면 되는 것이다.

 

3. 초기값 정하기

: 물론 1일때, 값이 1이라고 제시되었으니 초기값은 1

 

 

위와 같은 사고방식이 다른 DP문제에서도 통할 지 계속 풀어보자.