이번에도 오로지 내 머리로 푼 문제!! 드디어 DP의 방법을 깨우친 것인가🥹 100000도 되나?? 너무 오래 걸리는 거 아닌가??? 했는데 102로 딱 찍히는 쾌감이란 ㅎㅎㅎ
풀이
- 여러 개의 숫자를 직접 써보면서 규칙을 찾았다.
- 1을 빼는 건 무조건 가능하다.
- 2로 나누어지거나 3으로 나누어지거나 둘 다 나누어지거나 아예 안 나누어지는 4가지 경우가 가능하다.
- 그래서 나누어지면 나눈 수의 DP와 -1을 한 DP 중 최솟값을 찾아 DP에 넣으면 된다.
코드
import sys
input = sys.stdin.readline
N = int(input())
DP = [0, 0, 1, 1] # 2,3은 미리 넣어놓기
if N>3:
for i in range(4, N+1):
if i%2==0 and i%3==0:
DP.append(min(DP[i//2], DP[i//3], DP[i-1])+1)
elif i%2==0:
DP.append(min(DP[i//2], DP[i-1])+1)
elif i%3==0:
DP.append(min(DP[i//3], DP[i-1])+1)
else:
DP.append(DP[i-1]+1)
print(DP[N])- N이 4 이상이 아니면 for문을 돌 수가 없다.
(이젠 실수하지 않지) - 첫 번째 if문은 2와 3으로 모두 나누어지는 경우
- 두 번째 if문은 2로만 나누어지는 경우
- 세 번째 if문은 3으로만 나누어지는 경우
- 4 번째 if문은 아예 나누어지지 않는 경우
결과
