(DP) 백준 1463번 1로 만들기
내가 처음에 푼 방식의 코드
n = 10
count = 0
def solution(i):
global count
if i <= 1:
return False
count += 1
if i > 3:
if i % 3 != 0:
solution(i-1)
else:
solution(i//3)
else:
return
solution(n)
print(count)
나처럼 코드를 작성하면 DP를 잘못 이해한 것이다. DP는 점화식처럼 처음부터 수를 구해서 넣어보는 방식으로 풀어야한다고 한다.
정답코드
n = int(input())
dp = [0] * (n+1) # 메모이제이션, 값을 기록하기 위한 공간
for i in range(2, n+1): # 어차피 1은 자기 자신이므로 2부터 시작
dp[i] = dp[i-1] + 1 # 현재 값은 전 값의 +1이다. (마지막 조건에서 1을 빼기 때문에)
# 다만 2와 3으로 나누어 떨어질 경우에는 2와 3으로 나눈 값, 즉 전 값에다가 1을 더한 값 (전 값이므로)과 기존에 정의했던 값과 비교해서 작은 값을 정답으로 한다.
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2]+1)
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
print(dp[n])
Author And Source
이 문제에 관하여((DP) 백준 1463번 1로 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jwun95/DP-백준-1463번-1로-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)