아이테킨의 끄적끄적

점화식 $$ a_n = min(a_{n/3}+1, a_{n/2}+1, a_{n-1}+1) $$ 코드 # 1463 - 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//3]+1, dp[i]) if i%2 == 0: dp[i] = min(dp[i//2]+1, dp[i]) print(dp[n])

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP문제를 계속해서 풀면서 느끼는점은 결국 점화식을 생각해내는 것이 핵심 포인트인것 같다. 문제를 어떻게 쪼개고 반복해서 연산한다음 합칠것인지 충분히 고민하고 문제를 푸는게 오히려 더 빠르고 정확하다는 생각이 든다. 점화식 i번째에 빨강을 칠할 때 최소값 = i번째 빨강의 비용 + min(i-1번째 파랑의 최소값, i-1번째 초록의 최소값) 코드 # 1149 - RGB거리 #..