DP

문제 링크: https://neetcode.io/problems/climbing-stairs NeetCode neetcode.io 단순한 조합 문제라고 생각했다. 이런 비슷한 문제를 예전에 풀었지만 나중에야 기억이 났는데.. 암튼 초반에 그래서 삽질을 좀 했다. [초반 틀린 풀이]from itertools import permutationsclass Solution: def climbStairs(self, n: int) -> int: # 조합 구하기 + 순서 고려 result = 1 # consist of all 1s + possible 2s for i in range(1, n//2 + 1): # i = num of 2 goal..

import sys input = sys.stdin.readline DIV = 1000000009 dp = [1, 2, 4, 7] for _ in range(int(input())): # 방법의 총 수 dp, 순서 바꾸는 것도 포함이네.. n = int(input()) for i in range(len(dp), n): # 알아서 1, 2, 3이 각각 들어갈 것 -> 겹치는게 없음 dp.append((dp[i-1] + dp[i-2] + dp[i-3]) % DIV) print(dp[n-1]) 점화식은 발견 했는데 시간 초과, 메모리 초과를 어떻게 해결해야할지 생각해내는게 어려웠다. 이를 해결한 방법은 다음과 같다. 1. 모든 테스트케이스는 같은 DP 값을 가지니 DP를 global 하게 사용 2. 이미 있는..

import sys input = sys.stdin.readline n = int(input()) dp = [0] * (n+2) dp[0], dp[1], dp[2] = 0, 1, 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n]) 간단한 피보나치 문제!