N = int(input()) p = [0] + list(map(int,input().split())) dp = [0 for _ in range(N+1)] for i in range(1,N+1): for k in range(1,i+1): dp[i] = max(dp[i], dp[i-k] + p[k]) print(dp[i]) 작은 문제부터 생각해본다. 카드를 한개 사는법부터 dp[i] = 카드 i개 구매하는 최대 가격 , p[k] = k개가 들어있는 카드팩 가격 이라고 했을때 4 3 5 15 16 을 예시로 들자. dp[1] 은 언제나 p[1] 과 동일할 것이므로 3 일 것이다. dp[2] 는 dp[1] + p[1] 또는 p[2] 둘 중 큰 값일 것이므로 8 이다. dp[3] 은 dp[1] + p[2] , ..

import sys read = sys.stdin.readline word1, word2 = read().strip(), read().strip() l1, l2 = len(word1), len(word2) cache = [0] * l2 for i in range(l1): cnt = 0 # 새로운 값을 조회할때마다 0으로 초기화 for j in range(l2): if cnt < cache[j]: cnt = cache[j] # 앞에서부터 탐색하기 때문에 캐시에 저장된 cnt 값이 0보다 큰 경우가 뒤로 갈 수록 증가하고 # 캐시에 저장된 값이 현재 가장 긴 문자열의 길이이기 때문에 해당 값으로 cnt를 초기화하고 1을 더해줘야한다. elif word1[i] == word2[j]: cache[j] = cnt..

import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) cnt = 0 for i in arr: if i 0: arr[i+1] = arr[i]+arr[i+1] else: arr[i+1] = max(arr[i]+arr[i+1], arr[i+1], 0 print(max(arr)) 내가 풀이한 코드로 앞과 뒤를 더했을때 값이 -가 아니라면 해당 값을 넣고 -라면 0과 본인, 더한 값 중 가장 큰 값으로 초기화하여 나온 값 중 가장 큰 값을 출..

n = int(input()) dp = [0]*100001 dp[0] = 3 dp[1] = 7 for i in range(2,n+1): dp[i] = ((dp[i-1]*2) + dp[i-2]) % 9901 print(dp[n-1]) 풀이 n = 0 일 때, 사자를 놓지 않는 경우도 하나의 수로 가정한다고 했으므로 경우의 수는 1이 된다. n = 1 일 때 위와 같은 방법으로 사자를 둘 수 있다. 즉, 경우의 수는 3이다. n = 2 일 때를 생각해보자. 사자를 놓지 않는 방법은, n=1 일때 나올 수 있는 경우의 수만큼 둘 수 있다. 즉, 3이 된다. 사자를 왼쪽 혹은 오른쪽에 두는 방법은 총 4가지가 있음을 쉽게 유추할 수 있다. 따라서, n=2 일때 경우의 수는 7이다. 규칙이 보인다. 사자가 없는 ..

import sys input = sys.stdin.readline n = int(input()) dp = [1] * n boxs = list(map(int,input().split())) for i in range(1, n): for j in range(i): if boxs[j] < boxs[i]: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) 가장 긴 증가하는 부분 순열을 고르는 문제였다. 처음에는 그냥 큰 값이 있으면 앞의 작은 모든 값을 넣을 수 있어야 한다고 생각해서 헷갈렸는데 작은 걸 다음 큰 걸로 넣는 걸 반복하는 형식임을 깨닫고 바로 풀 수 있었다.

import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) starr = [] for _ in range(2): temp = list(map(int, input().split())) starr.append(temp) for i in range(1, n): if i == 1: starr[0][i] += starr[1][i-1] starr[1][i] += starr[0][i-1] else: starr[0][i] += max(starr[1][i-1], starr[1][i-2]) starr[1][i] += max(starr[0][i-1], starr[0][i-2]) print(max(starr[0][-1],starr[1..