https://www.acmicpc.net/problem/1106 #1.입력C,N=map(int,input().split()) #C:people,N:citycost,people=[0],[0]for _ in range(N): c,p=map(int,input().split()) cost.append(c) people.append(p)#2.자료형 정의dp=[float('inf') for _ in range(C+1)]dp[0]=0 # 0명 모집 비용은 0#3.동작함수for n in range(1,N+1): for c in range(1,C+1): case1=min(dp[c],((c+people[n]-1)//people[n])*cost[n]) case2 = floa..

https://www.acmicpc.net/problem/2293 #1.입력N,K=map(int,input().split())coin=[0] #0은 더미for _ in range(N): coin.append(int(input()))#2.자료형 정의dp=[0 for _ in range(K+1)]#3.동작함수for n in range(1,N+1): for k in range(1,K+1): case=0 if 0자꾸 메모리 초과가 나서 질문 게시판을 보니 차원 배열을 써야하는 문제라고 알려주셨다. 그래서 2차원 배열을 1차원 배열로 바꾸어 풀었더니 해결되었다.

https://www.acmicpc.net/problem/2294N,K=map(int,input().split())coin=[0] #0은 더미for _ in range(N): coin.append(int(input()))dp=[[100001]*(K+1) for _ in range(N+1)]for n in range(1,N+1): for k in range(0,K+1): if k==0: dp[n][k]=0 continue case1=100001 if k>=coin[n]: #첫 시작일 때 if n==1: if k%coin[n]==0: ..

https://www.acmicpc.net/problem/1149N=int(input())dp=[]for i in range(N): dp.append(list(map(int,input().split())))for i in range(1,N): #현재가 빨간색 지붕이라면->이전 지붕이 초록색/파란색이여야함 dp[i][0]+=min(dp[i-1][1],dp[i-1][2]) #현재가 초록색 지붕이라면->이전 지붕이 빨간색/파란색이여야함 dp[i][1]+=min(dp[i-1][0],dp[i-1][2]) #현재가 파란색 지붕이라면->이전 지붕이 빨간색/초록색이여야함 dp[i][2]+=min(dp[i-1][0],dp[i-1][1])print(min(dp[N-1][0],dp[N-..

https://www.acmicpc.net/problem/9095 T=int(input())for _ in range(T): n=int(input()) dp=[0 for _ in range(n+1)] for i in range(1,n+1): if i dp[i]=dp[i-1]+dp[i-2]+dp[i-3]인 이유→ 마지막에 더한 수가 1,2,3 중 어떤 것인지로 나눔 마지막에 +1를 붙였다면→ 그 앞부분은 i-1을 만드는 방법이어야 함→ dp[i-1]가지 마지막에 +2를 붙였다면→ 그 앞부분은 i-2을 만드는 방법이어야 함→ dp[i-2]가지 마지막에 +3를 붙였다면→ 그 앞부분은 i-3을 만드는 방법이어야 함→ dp[i-3]가지 따라서 dp[i]를 만들기 위해서는 dp[i-1]..

https://www.acmicpc.net/problem/2579 n = int(input())stair = [0] # 1-based indexingfor _ in range(n): stair.append(int(input()))if n == 1: print(stair[1])elif n == 2: print(stair[1] + stair[2])else: dp = [0] * (n + 1) dp[1] = stair[1] dp[2] = stair[1] + stair[2] for i in range(3, n + 1): dp[i] = max( dp[i - 2] + stair[i], # 2칸 오르기 ..

https://youtu.be/eJC2oetXaNk?si=n6ZFPnv56clCkA8f코드없는 프로그래밍님의 영상이 가장 이해하기 좋았다. - Problem이 Sub Problem으로 쪼개질 때- Sub Problem의 solution으로 Problem의 solution을 구할 수 있을 때- 이런 Sub Problem들이 겹칠 때 fib_array=[0,1]def fib_td(n): #Top-down if n하지만 Top-Down 방식은 recursion depth exceeded 에러가 발생할 수도 있음. def fib_dp(n): #Bottom-up fib_array=[0,1] for i in range(2,n+1): num=fib_array[i-1]+fib_array[i..