맛대의 블로그

https://www.acmicpc.net/problem/12865 N,K = map(int,input().split()) backpack = [0]*(K+1) for _ in range(N): W,V = map(int,input().split()) for i in range(len(backpack))[::-1]: if backpack[i] and i + W

dp 활용 시작지점부터 현재 좌표까지의 합을 dp에 기록 dp에 기록된 값을 활용하여 값 계산 (x1,y1)~(x2,y2)의 합은 dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] (이건 겹치는 부분) 그림으로 그리면 이해가 쉬울텐데 그림 그릴 도구가 없다.. import sys N,M = map(int,sys.stdin.readline().split()) arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)] dp = [[0]*(N+1) for _ in range(N+1)] for i in range(1,N+1): for j in range(1,N+1): if j == 0: dp[..

https://www.acmicpc.net/problem/1932 dp 적용 삼각형을 위에서 부터 내려오면서 각 요소를 선택했을때 최대 값만 dp에 기록 예시의 경우 dp[0]에는 7, dp[1]에는 10,15가 기록이 됨(7+3,7+8), dp[2]에는 18,16,15가 기록이 됨 (10+8, 15+1, 15+0) import sys def solve(): for i in range(1,n): # for j in range(i+1): if 0

https://www.acmicpc.net/problem/2407 1C0 = 1 , 1C1=1 2C0 = 1 , 2C1 = 2 , 2C2 = 1 3C0 = 1 , 3C1 = 3 , 3C2 = 3 , 3C3 = 1 4C0 = 1 , 4C1 = 4 , 4C2 = 6 , 4C3 = 4, 4C4 = 1 nCm = (n-1)C(m-1) + (n-1)C(m) 이라는 규칙이 있음을 활용 (n-1)C(m-1) = (n-2)C(m-2) + (n-2)C(m-1) (n-1)C(m) = (n-2)C(m-1) + (n-2)C(m) 계산기 (n-2)C(m-1)을 이미 계산했는데 또 계산해야 하는 상황 발생 dp를 활용하여 계산 횟수를 줄임 def combination(a,b): if dp[a][b]: return dp[a][b]..

https://www.acmicpc.net/problem/1149 앞 뒤 집과 색이 달라야 함, R G B 세가지 색을 사용하여 집을 색칠 집을 하나 칠하고 그 전집과 색이 다르게만 칠하면 자연스럽게 완성 최소 값을 구해야 하는데, 그 전집의 색, 지금까지의 값만 중요 DP를 이용하여 R,G,B색을 칠했을 경우 최소 비용을 누적하여 저장하는 형태 현재 집을 R 선택했다면, 전집이 G,B일때 값을 비교하여 둘 중 최소인 것만 저장 def check(i): for j in range(3): # 이번 집의 RGB 선택 pay = total[i][j] # 이번 집 색칠에 드는 비용 temp = [] for k in range(3): # 전집 색 선택 if k != j: # 같은색 배제 temp.append(dp..