본문 바로가기

Algorithm 💡272

[백준 9095번] 1, 2, 3 더하기 def dynamic(n): if n == 1: return 1 if n == 2: return 2 if n == 3: return 4 dp = [0]*(n+1) dp[1],dp[2],dp[3] = 1, 2, 4 for i in range(4, n+1): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] return dp[n] t = int(input()) result = [] for i in range(t): n = int(input()) result.append(dynamic(n)) for i in result: print(i) 이번 문제는 주어진 정수 N을 1, 2, 3의 합으로 만들 수 있는 경우의 수를 구하는 문제이다. n=1, n=2, n=3 인 경우를 DP 테이블에 저장하고 n.. 2023. 3. 10.
[백준 2156번] 포도주 시식 n = int(input()) weight = [0]*10000 dp = [0]*10000 for i in range(n): weight[i] = int(input()) dp[0] = weight[0] dp[1] = weight[0] + weight[1] dp[2] = max(weight[2]+weight[0], weight[2]+weight[1], dp[1]) for i in range(3,n): dp[i]=max(weight[i]+dp[i-2], weight[i]+weight[i-1]+dp[i-3],dp[i-1]) print(max(dp)) 이번 문제는 이전에 풀었던 '2579번 - 계단 오르기' 문제와 유사한 문제로, 연속 3개의 포도주를 마시지 못한다는 조건 하에 최대로 마실 수 있는 포도주의 양.. 2023. 3. 8.
[백준 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.

티스토리툴바