황소개발자

아래 코드를 붙이면 컴파일 된다. g++ -o main main.cpp main 은 파일이름이니 맞춰서 바꾸면된다. * g++ 은 sudo apt install g++ 로 설치해준다.

5 1000 입력했을 때, 11 2 가 나오는가? 안나온다면 중복을 해결하지 못한것이여. 그리고 n == k 일 때, 0 1 이 나와야혀. 코드는 다음과 같네 dp2 로 중복 개수를 헤아렷네. n, k = map(int, input().split()) if n == k: print(0) print(1) exit() dp = [-1] * 150001 dp2 = [1] * 150001 flag = False dist = -1 count = 0 dp[n] = 0 q = [n] q2 = [] while q: now = q.pop(0) if now + 1 = 0: if dp[now - 1] == dp[now] + 1: dp2[now - 1] += dp2[now] elif dp[now - 1] == -1: if n..

올바른 괄호가 되기위해서는 ( * * * * ) * * * * * * 이런식. 이 때, 첫번째 괄호를 1번째, 두번째 괄호를 k 번째라고하자. 그러면 괄호안에 쌓여진 공간의 개수는 k - 2 이고, 오른쪽에 공간의 개수는 n - k 개이다. dp[n] = dp[k - 2] * dp[n - k] (k = 2 ~ n) 이다. import sys input = sys.stdin.readline t = int(input()) lst = [] for _ in range(t): lst.append(int(input())) dp = [0] * 5001 dp[0] = 1 for i in range(2, 5001, 2): for j in range(2, i + 1, 2): dp[i] += (dp[j - 2] * dp[i..

초등학교 4학년.. 0 ~ 20 배열 두개 만들어줘서 번갈아가면서 업데이트해주면 됩니다 수 하나씩 꺼내면서 고려해주는 것이죠. n = int(input()) lst = list(map(int, input().split())) dp1 = [0] * 21 dp2 = [0] * 21 dp1[lst[0]] = 1 for i in range(1, n - 1): for j in range(21): if j + lst[i] = 0: dp2[j - lst[i]] += dp1[j] dp1 = dp2 dp2 = [0] * 21 print(dp1[lst[-1]])

m 크기 배열을 두개 만들어주고 서로 교차해주면서 업데이트 해나가면 된다. n, m 범위도 크지 않기에 가능하다. n, s, m = map(int, input().split()) lst = list(map(int, input().split())) dp1 = [0 for i in range(m + 1)] dp2 = [0 for i in range(m + 1)] dp1[s] = 1 for v in lst: for i in range(m + 1): if dp1[i]: if i + v = 0: dp2[i - v] = 1 dp1 = dp2 dp2 = [0] * (m + 1) ans = -1 for i in range(m, -1, -1): if dp1[i]: ans = i break print(ans)

이거가 이글부터 보라는건 아닌데, 이 n 의 범위부터 봐라 범위가 100이하다 n ^ 2 돌려도 작은 수다 그래서 이중포문 맘편히 돌릴 수 있다. d[i] : i 일때 최대 값 a, c, v 는 한개의 세트로 묶어서 생각할 수 있다. 그리고 마지막에 오는게 제일 이득이다 a, c, v, v, v 이런식으로 올지언정 이 복붙관련 키들이 제일 마지막에 와야 이득 dp[11] 도 결국은 dp[7] 에서 a, c, v, v 해서 온것이다. n = int(input()) dp = [0 for i in range(101)] dp[0] = 0 dp[1] = 1 dp[2] = 2 for i in range(3, 101): dp[i] = dp[i - 1] + 1 for j in range(i - 3, -1, -1): d..

생각해보자 동전의 종류는 1원, 5원, 12원 자, 15원을 만들고 싶어 그러면 14원에서 1원을 더하거나, 10원에서 5원을 더하거나, 3원에서 12원을 더하거나 음 구현해보자 import sys input = sys.stdin.readline n, k = map(int, input().split()) lst = [] dp = [999999999] * (k + 1) dp[0] = 0 for _ in range(n): lst.append(int(input())) lst.sort() for price in lst: for i in range(price, k + 1): dp[i] = min(dp[i - price] + 1, dp[i]) print(dp[-1] if dp[-1] != 999999999 else..

첫번째 동전을 생각했을 때, 두번째 동전을 생각했을 때,, .... 하나씩 고려하면서 더해나가는거에요 import sys input = sys.stdin.readline n, k = map(int, input().split()) lst = [] dp = [0] * (k + 1) dp[0] = 1 for _ in range(n): lst.append(int(input())) lst.sort() for price in lst: for i in range(price, k + 1): dp[i] += dp[i - price] print(dp[k])