백준 15990번 - 1로 만들기
n = int(input())
dp = [0] * (n+1)
for i in range(2, n+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[n])풀이(메모이제이션을 통한 풀이) - dp문제
1. dp에 0으로 다 초기화해둔다.
2. 메모이제이션을 통해서 dp에 n까지의 최솟값을 저장해둔다.
(이 때 모든 경우의 수를 고려해야 해서 3으로 나눌 떄, 2로 나눌 때, +1할 때를 다 고려한다.
3. dp[n]을 출력한다.
Author And Source
이 문제에 관하여(백준 15990번 - 1로 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@aksmf1442/백준-15990번-1로-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
