느낌표 공장

n = int(input()) cards = [0] + list(map(int, input().split())) dp = [0 for _ in range(n+1)] # 각 자리에는 카드 i개를 구매하는 최대 가격이 저장됨 for i in range(1, n+1): for j in range(1, i+1): # i가 4면 (3, 1), (2, 2), (1, 3)일 때를 보는것 dp[i] = max(dp[i-j] + cards[j], dp[i]) # i개 구매할때의 최대 가격 갱신 print(dp[n]) 풀이 포인트 dp 리스트의 자리 i에는 카드 i개를 구매하는 최대 가격이 저장된다. 이중 for문을 돌면서 카드 i개를 구매하는 경우, j가 1부터 돌면서 dp[i-j] + cards[j] 의 값들 중, 최..

n = int(input()) # 수열의 크기 numbers = list(map(int, input().split())) # 수열 dp = [0 for _ in range(n)] # dp 배열 answer = -1001 # 주어진 수열의 원소 범위보다 더 작게 설정 for i in range(n): dp[i] = max(dp[i-1] + numbers[i], numbers[i]) # 이전까지의 연속 합 vs 현재 숫자 (현재 숫자 택하면 꼬리자르기) answer = max(dp[i], answer) # 현재까지의 합이 더 크다면 answer 갱신 print(answer)

n = int(input()) # 수열의 크기 numbers = list(map(int, input().split())) # 수열 dp = [1 for _ in range(n)] # dp 배열 만들기 (자기자신 1이니까 1로 초기화) answer = 1 # 가장 긴 증가하는 부분 수열 길이 for i in range(n): for j in range(i): # 현재 위치(i)보다 전의 숫자(j)가 작은지 확인 if numbers[j] < numbers[i]: dp[i] = max(dp[i], dp[j]+1) # 결국 i위치의 이전 길이중 최댓값에 +1 하게 된다 answer = max(dp[i], answer) # 가장 긴 이라고 했으니, 길어졌다면 큰 값으로 갱신 print(answer)

n = int(input()) # 계단의 수 stairs = [int(input()) for _ in range(n)] # 계단 if n == 1: print(stairs[0]) else: dp = [0 for _ in range(n)] dp[0] = stairs[0] # 1번 계단 dp[1] = stairs[0] + stairs[1] # 1번 + 2번 계단 밟음 for i in range(2, n): # 1. 현재 계단 + 이전의 계단 + 전전전의 계단 밟은 경우 # 2. 현재 계단 + 전전의 계단 밟은 경우 # 두 경우 중 더 큰 값을 선택 dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i]) print(dp[n-1]) 점화식을 찾는..

import sys input = sys.stdin.readline n, m = map(int, input().split()) # 수의 개수 n, 합을 구해야 하는 횟수 m numbers = list(map(int, input().split())) # n개의 수 # dp 리스트 만들기 dp = [0 for _ in range(n+1)] for i in range(n): dp[i+1] = dp[i] + numbers[i] for _ in range(m): i, j = map(int, input().split()) print(dp[j] - dp[i-1]) 풀이 먼저 dp[i+1]에 numbers[i]까지(numbers[:i+1])의 합을 저장하여 dp리스트를 만든다. i와 j가 주어졌을 때, i는 구간의 시..

n = int(input()) arr = [0 for _ in range(1000001)] arr[1] = 1 arr[2] = 2 for i in range(3, n+1): # 더해서 저장하고 마지막에 나머지 구하면 숫자가 너무 커지니, 나머지로 넣어준다. arr[i] = (arr[i-1] + arr[i-2]) % 15746 print(arr[n]) 규칙 : 크기가 n일 때의 가짓수 = 크기가 n-1일 때의 가짓수 + 크기가 n-2일 때의 가짓수

탑다운 방식 (재귀) tc = int(input()) dp_l = [0, 1, 2, 4] + [0 for _ in range(9)] # 11까지의 방법을 담을 리스트 # 규칙 : 정수 n을 1, 2, 3으로 나타낼 수 있는 방법 수 = 정수 n-3 , n-2, n-1 을 나타낼 수 있는 방법 수를 다 더한 것 # dp 함수 def dp(n): # 리스트에 현재 n을 나타낼 수 있는 방법의 수가 비어 있다면 if not dp_l[n]: # 정수 n-1의 방법의 수가 저장되어 있는지 확인 -> 안되어있다면 또 들어감 dp(n-1) # n-1까지 다 저장되어 있으면 현재 n의 정수를 나타낼 수 있는 방법의 수 저장. dp_l[n] = dp_l[n-3] + dp_l[n-2] + dp_l[n-1] for i in..

n = int(input()) arr = [0 for _ in range(101)] arr[1] = 1 arr[2] = 1 arr[3] = 2 for i in range(3, n+1): # 규칙 : 현재 수 = 전의 수 + 전전 수 arr[i] = arr[i-1] + arr[i-2] print(arr[n])

n = int(input()) answer = [0 for _ in range(10000)] answer[1] = 1 answer[2] = 3 answer[3] = 5 for i in range(4, n+1): answer[i] = (answer[i-1] + 2 * answer[i-2]) % 10007 print(answer[n]) 규칙 : 2xn 크기의 직사각형 채우는 방법의 수 = 2x(n-1) 크기의 직사각형 채우는 방법의 수 + 2x(n-2) 크기의 직사각형 채우는 방법의 수 * 2

DFS 풀이 # (이전의 색, 여태까지 칠한 칸 수, 현재 인덱스) # 1행부터 n-2행까지 (마지막이 n-1행) 실행함 def paint(before, cnt, i): global answer # 지금까지 칠한 칸 수가 이미 answer에 들어있는 값보다 작으면 볼 필요 없다. 끊자 if answer 다음에 칠할 수 있는 색은 흰색, 파란색 if before == 'W': ..