풀캠정글러

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys input = sys.stdin.readline n, k = map(int, input().split()) C = [] for i in range(n) : C.append(list(map(int, input().split()))) f = [[0 for i in range(k + 1)] for i in range(n)] for i in range(n) : w, v = C[i][0], C[i][1] for j in range(1, k + 1) : if j >= w : f[i][j] = max(f[i-1][j], f[i-1][j - w] + v) else : f[i][j] = f[i-1][j] print(f[n-1]..

1 2 3 4 5 6 7 8 9 10 11 testcase = int(input()) for t in range(testcase) : n = int(input()) C = list(map(int, input().split())) m = int(input()) DP = [0 for i in range(m + C[-1] + 1)] DP[0] = 1 for coin in C : for i in range(1, m + 1) : DP[i] = DP[i] + DP[i - coin] print(DP[m]) cs IDEA 50원, 100원, 500원 동전이 있다고 하자. 5000원을 만드는 경우는, 4500원을 만드는 경우에 500원 하나를 더하거나, 4900원을 만드는 경우에 100원 하나를 더하거나, 4950원을 ..

1 2 3 4 5 6 n = int(input()) list = [0, 1, 0] for i in range(n) : list[2] = (list[0] + list[1]) % 15746 list[0], list[1] = list[1], list[2] print(list[min(n, 2)]) cs IDEA 길이 n의 수열은 길이 n-1의 수열에 1을 붙이거나, 길이 n-2의 수열에 00을 붙여서 만들어진다. 점화식으로 나타내면 f(n) = f(n-1) + f(n-2)인 피보나치 수열이다. n-2 이전의 값은 f(n)을 구하는데 필요없으므로, dp는 3칸만 있으면 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 import sys input = sys.stdin.readline sys.setrecursionlimit(10**8) alph = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ') digit = list('0123456789') dic = {} for i in range(26) : dic[alph[i]] = i + 1 for i in range(26) : for j i..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import sys input = sys.stdin.readline from collections import deque testcase = int(input()) for j in range(testcase) : n = int(input()) V = {} parent = [0 for i in range(n + 1)] for i in range(1, n + 1) : V[i] = [] l = list(map(int, input().split())) for i in range(n) : V..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import sys input = sys.stdin.readline from collections import deque n = int(input()) T = [] gone = {} for i in range(n) : T.append(list(input())) for j in range(n) : gone[(i, j)] = False T.append([None for i in range(n + 1)]) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def BFS(X, Y) : que = d..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 import sys input = sys.stdin.readline from collections import deque n, m = map(int, input().split()) V = {} parent = [0 for i in range(n + 1)] for i in range(1, n + 1) : V[i] = [] for i in range(m) : l = list(map(int, input().split())) for i in range(1, l[0]) : V[l[i]].append(l[i+1]) parent[l[i+1]] = parent..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import sys input = sys.stdin.readline from collections import deque Vn = int(input()) V = {} for i in range(1, Vn + 1) : V[i] = [] B = [0 for i in range(Vn + 1)] parent = [0 for i in range(Vn + 1)] for i in range(1, Vn + 1) : l = list(map(int, input().split())) B[i] = l[0] for j in range(2, len(l)) : V[l[j]].appe..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import sys input = sys.stdin.readline from heapq import heappush, heappop Vn, En = map(int, input().split()) V = {} parent = [0 for i in range(Vn + 1)] for i in range(1, Vn + 1) : V[i] = [] for i in range(En) : v1, v2 = map(int, input().split()) V[v1].append(v2) parent[v2] = parent[v2] + 1 heap = [] for i in range(1, Vn + 1)..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import sys input = sys.stdin.readline from collections import deque Vn = int(input()) V = {} for i in range(1, Vn + 1) : V[i] = [] B = [0 for i in range(Vn + 1)] parent = [0 for i in range(Vn + 1)] for i in range(1, Vn + 1) : l = list(map(int, input().split())) B[i] = l[0] for j in range(1, len(l) - 1) :..