WoohyunKing의 개발 성장일지

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개의 포도주를 마시지 못한다는 조건 하에 최대로 마실 수 있는 포도주의 양..

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)가 주어진 물건들을 가지..

# 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..

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]) 이번 문제는 다음과 같은..

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..

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 값에서부터..

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 방식을 사용하여 문제를 해결할 수 있었다 :) (재귀 함수를 이용한 탑-다운이 아니라, 반복문을 이용한 바텀-업 방식을 사용했다면 더 빠르게 풀이할 수 있었을 것이다.)

이번 문제는 간단히 정리하자면 주어진 n의 자리수를 가지며 00과 1을 가지고 만들 수 있는 문자열의 개수를 구하는 문제이다. 처음에 이 문제를 보았을 때 왜 이게 DP 문제이고, 어떤 방식으로 문제를 풀어야 할지 감도 오지않았고, 결국 30분정도 고민하다가 풀이 접근 방법에 대해 이해하기 위하여 다른 분의 풀이를 참고하였다 😢 다른 분들의 풀이마저도 처음에 이해하기 어려웠기 때문에 직접 n=1(일의 자리수)부터 n=5(만의 자리수) 까지 종이에 적어보면서 이해해보기로 하였다. 다른 분들의 풀이를 참고하고 경우의 수를 직접 손으로 적어보니 이 문제가 왜 DP 문제인지 새삼 알 수 있었다. 1) 문제 접근법 n = 1 : 1 n = 2 : 00, 11 n = 3 : 100, 001, 111 n = 4 : ..

import sys input = sys.stdin.readline def w(a,b,c): if a 20: return w(20,20,20) if dp[a][b][c]: return dp[a][b][c] if a < b and b < c: dp[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c) return dp[a][b][c] dp[a][b][c] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1) return dp[a][b][c] dp = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)] while True: a, b, c = map(int,..

n = int(input()) dp = [0]*41 count_r = 0 count_d = 0 def fib_recursive(n): # 일반적인 재귀함수 피보나치 수열 계산 global count_r if n==1 or n==2: count_r += 1 return 1 else: return fib_recursive(n-1) + fib_recursive(n-2) def fib_dynamic(n): # 동적계획법을 사용한 피보나치 수열 계산 global count_d if n==1 or n==2: if dp[n] == 0: dp[n] = 1 return dp[n] else: if dp[n] != 0: return dp[n] else: count_d += 1 dp[n] = fib_dynamic(n-1) +..