N = int(input()) arr = list(map(int, input().split())) dp = [1] * N for i in range(1, len(arr)): for j in range(i): if arr[i] < arr[j]: dp[i] = max(dp[j] + 1, dp[i]) print(max(dp)) 먼저 항상 모든 배열의 값들을 특정 값으로 초기화하거나 경우의 수를 특정 범위까지 입력하고 최적의 해를 각 인덱스에 넣어야 한다는 걸 잊지말자. dp[i]는 계속 앞의 값과 비교하면서 최대값을 구해야 하는데, 만약 j가 여러 개고 그 값의 고저가 모두 다른 경우를 가정하면 앞의 j가 2라서 +1이 되어 dp[i] =3 일때 뒤의 j가 1이라 +1은 2인 상황이면 현재 자신의 dp[i]가..

n = int(input()) s = [0] * 301 dp = [0] * 301 for i in range(n): s[i] = int(input()) dp[0] = s[0] dp[1] = s[0] + s[1] dp[2] = max(s[1] + s[2], s[0] + s[2]) for i in range(3, n): dp[i] = max(dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i]) print(dp[n - 1]) 첫번째 3개의 계단과 두번째 3개의 계단을 3개 연속하지 않고 최대의 값을 구하는 식을 구하지 못했다. 최적의 해는 먼저 각 dp에 최대의 값을 2까지 넣어준다. 이 최대의 값은 해당하는 계단의 순번까지 밟고 올라오는 최대의 수이며 그 값은 첫번째는 자신의 ..

1. 경우의 수일 경우 1부터 차근히 경우의 수를 구하고 수식을 찾는다. 경우의 수가 변하는 분기를 기준으로 리스트에 값을 넣고 점화식을 이용하여 문제를 푼다. 2. 최적의 값 혹은 해를 찾는 경우, 각 인덱스 값에 현재 가장 최적인 값을 찾는 식을 찾아야 한다. 일단 모든 리스트를 최소의 최적 값으로 초기화한다. 이후 작은 값부터 최적의 값을 채우는 경우를 찾아야 한다. 보통 단계로 쪼개져 비교하는 경우와 배열 중 가장 긴 무언가를 찾는 경우, 혹은 리스트를 가장 큰 값 혹은 작은 값으로 유도하는 경우가 있다. 이를 위해서 쪼개는 경우는 쪼개진 경우에서 각각 최적의 값을 채우고 반복되서 비교되는 식을 세우면 어느 정도 해결이 된다. (계단 오르기) 가장 긴 무언가를 찾는 경우는 각 인덱스의 값과 인덱스..

n = int(input()) d = [0] * 1001 d[1], d[2] = 1, 2 for i in range(3, n+1): d[i] = d[i-1] + d[i-2] print(d[n]%10007) 일반적인 dp문제로 점화식을 세워야 한다. 잘 생각하고 항상 점화식을 세우자. 이건 기본적인 문제 유형이다. N의 길이가 1일때는 경우의 수가 1, 2일때는 경우의 수가 2, 3일때는 3, 4일때는 5, 5일때는 8이다. 이는 1의 길이와 2의 길이를 가진 타일을 n-1의 길이일 때와 n-2의 길이일 경우 두 가지가 있다는 것을 기반으로 3부터는 이 두 가지 경우가 합쳐진 경우의 수가 정답이 되는 것이다. 그래서 점화식이 n = n-1의 경우의 수 + n-2의 경우의 수가 된다는 것을 알 수 있다.

N = int(input()) def sol(n): if n == 1: return 1 elif n == 2: return 2 elif n == 3: return 4 else: return sol(n-1) + sol(n-2) + sol(n-3) for i in range(N): n = int(input()) print(sol(n)) 1 = 1/ 2 = 2/ 3 = 4/ 4 = 7/ 5 = 13 위의 값은 경우의 수 이며 4와 5를 보면 해당 값들이 전의 값 3개의 더한 것임을 알 수 있다. 그러므로 점화식을 세워서 풀어 재귀로 풀었으나 하향식을 이용하여 배열에 값을 넣어두는 방식도 얼마든지 이용할 수 있다. T = int(input()) for i in range(T) : n = int(input()) ..

N = int(input()) fibo = list(0 for _ in range(N+1)) fibo[1] = 1 for i in range(2, N+1): fibo[i] = fibo[i-1] + fibo[i-2] print(fibo[-1]) 각 인덱스에 현재 숫자의 피보나치 수를 입력하고 fibo = fibo[-1] + fibo[-2] 라는 식을 대입하면 된다.