이것저것 기록 블로그

n = int(input()) array = [] for j in range(n): array.append(int(input())) d = [0] * n d[0] = array[0] if n == 1: print(d[0]) elif n == 2: d[1] = array[0] + array[1] print(d[n-1]) elif n > 2: d[1] = array[0] + array[1] d[2] = max(array[0] + array[2], array[1] + array[2]) for i in range(3, n): d[i] = max(d[i-2] + array[i], array[i] + array[i-1] + d[i-3]) print(d[n-1])

n = int(input()) array = [] for i in range(n): array.append(int(input())) d = [0] * len(array) d[0] = array[0] if n == 2: d[1] = array[0] + array[1] elif n > 2: d[1] = array[0] + array[1] d[2] = max(d[1], array[1] + array[2], array[0] + array[2]) for i in range(3, n): d[i] = max(array[i] + d[i-2], d[i-1], array[i] + array[i-1] + d[i-3]) print(max(d)) 그냥 전형적인 dp 문제였는데 왜이렇게 어렵게 느껴졌을까... 흠....

n = int(input()) period = [] price = [] for i in range(n): a, b = map(int, input().split()) period.append(a) price.append(b) d = [0] * 20 d[period[0]-1] = price[0] for i in range(1, n): idx = period[i] + i - 1 if idx == 0: d[idx] = max(d[0], max(d[:i]) + price[i]) else: d[idx] = max(max(d[:idx+1]), max(d[:i]) + price[i]) print(max(d[:n])) 손으로 일일이 써가면서 했던 문제. 하나하나씩 dp table을 채워가며 답을 구했던 문제.

n = int(input()) graph = [] for i in range(n): graph.append(list(map(int, input().split()))) d = [[0 for _ in range(i)] for i in range(1, n+1)] d[0][0] = graph[0][0] for i in range(1, n): for j in range(0, i+1): left = 0 right = 0 if j == 0: left = 0 right = d[i-1][j] elif j == i: left = d[i-1][j-1] right = 0 else: left = d[i-1][j-1] right = d[i-1][j] d[i][j] = max(left, right) + graph[i][j] pri..