728x90
조코딩
-
[Python][백준] 9095번 문제 1, 2, 3 더하기 해결 | DP는 어려워Algorithm/백준 2022. 3. 12. 10:00
동적 계획법(dynamic programming, DP) DP 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. DP의 핵심 작은 부분을 기억하는 것이다. 왜냐하면 Optimal Structure가 있는 문제를 풀 때 구조를 새로 구할 필요없이, 방금 전 기억한 작은 부분을 불러오면 더 빠르고, 효율적으로 구할 수 있기 때문이다. 오늘은 DP를 이용하여 푼 1, 2, 3 더하기 문제를 풀어보겠다. lines = int(input()) cases = list(int(input()) for _ in range(lines)) for c in cases: dp = [0, 1, 2, 4] + [0 for _ in range(c)] for i in range(4, c+1): dp[i] = dp[i-3] + dp[i..