본문 바로가기

Algorithm 💡/DP41

[백준 12865번] 평범한 배낭 n, k = map(int,input().split()) list = [(0,0)] for i in range(n): list.append(tuple(map(int,input().split()))) dp = [[0] * (k+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1, k+1): w = list[i][0] v = list[i][1] if j < w: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j-w] + v,dp[i-1][j] ) print(dp[n][k]) 이번 문제는 DP 문제 유형 중 유명한 문제 중 하나로, 최대 무게가 정해진 가방에 무게(w)와 가치(v)가 주어진 물건들을 가지.. 2023. 3. 8.
[백준 10844번] 쉬운 계단 수 # 1 2 3 4 5 6 7 8 9 # [1]0, [1]2, [2]1, [2]3, [3]2, [3]4, [4]3, [4]5, [5]4, [5]6, [6]5, [6]7, [7]6, [7]8, [8]7, [8]9, [9]8 # [10]1, [12]1, [12]3, [21]0, [21]2, [23]2, [23]4, [32]1, [32]3, [34]3, [34]5, [43]2, [43]5 n = int(input()) dp = [[0]*10 for i in range(101)] for i in range(1,10): dp[0][i] = 1 for i in range(n): for j in range(10): if j == 0: dp[i+1][j+1] += dp[i][j] elif j == 9: dp[i+1][j.. 2023. 3. 7.
[백준 2579번] 계단 오르기 n = int(input()) score = [0]*n dp = [0]*n for i in range(n): score[i] = int(input()) if n == 1: print(score[0]) elif n == 2: print(score[0]+score[1]) elif n == 3: print(score[0]+max(score[1],score[2])) else: dp[0] = score[0] dp[1] = score[0] + score[1] dp[2] = score[2] + max(score[1],score[0]) for i in range(3,n): dp[i] = score[i] + max(score[i-1] + dp[i-3], dp[i-2]) print(dp[n-1]) 이번 문제는 다음과 같은.. 2023. 3. 5.
[백준 1149번] RGB거리 import sys input = sys.stdin.readline n = int(input()) area = [[0]*3 for _ in range(n)] dp = [[0]*3 for _ in range(n)] for i in range(n): area[i] = list(map(int,input().split())) dp[0] = area[0] for i in range(1,n): for j in range(3): if j == 0: dp[i][j] = area[i][j] + min(dp[i-1][1], dp[i-1][2]) elif j == 1: dp[i][j] = area[i][j] + min(dp[i-1][0], dp[i-1][2]) else: dp[i][j] = area[i][j] + min(d.. 2023. 3. 5.
[백준 1463번] 1로 만들기 n = int(input()) dp = [0]*3000003 for i in range(1,n+1): if dp[i+1] == 0: dp[i+1] = dp[i] + 1 else: dp[i+1] = min(dp[i+1], dp[i]+1) if dp[i*2] == 0: dp[i*2] = dp[i] + 1 else: dp[i*2] = min(dp[i*2], dp[i]+1) if dp[i*3] == 0: dp[i*3] = dp[i] + 1 else: dp[i*3] = min(dp[i*3],dp[i]+1) print(dp[n]) 이번 문제는 입력받은 N을 '2로 나누기', '3으로 나누기', '1 빼기' 이 세가지 연산을 가지고 1을 만들 수 있는 최소 연산횟수를 구하는 문제였다. 처음에는 입력받은 N 값에서부터.. 2023. 3. 4.
[백준 9461번] 파도반 수열 def solution(n): dp = [0]*101 dp[1], dp[2], dp[3], dp[4], dp[5] = 1, 1, 1, 2, 2 if n=6) = P(n-1) + P(n-5) 위와 같은 점화식이 도출되고 나서, DP 알고리즘 중에서도 Top-Down 방식을 사용하여 문제를 해결할 수 있었다 :) (재귀 함수를 이용한 탑-다운이 아니라, 반복문을 이용한 바텀-업 방식을 사용했다면 더 빠르게 풀이할 수 있었을 것이다.) 2023. 3. 2.

티스토리툴바