WoohyunKing의 개발 성장일지

n = int(input()) array = list(map(int,input().split())) if n == 1: print(array[0]) else: dp = [0]*n dp[0] = array[0] for i in range(1,n): dp[i] = max(array[i],dp[i-1] + array[i]) print(max(dp)) 이번 문제는 주어진 수열에서 연속된 수열 중 가장 합이 큰 수열의 합을 구하는 문제이다. 처음에는 어떻게 경우의 수를 구해야할지 고민했었는데 곰곰히 생각해보니 첫번째 수부터 연속된 수열을 찾는 경우, 결국에는 마지막 수까지 고려를 해야한다는 것을 깨닫고 DP 알고리즘을 사용하여 첫번째 수부터 시작해서 최적의 값을 DP 테이블에 저장해가는 방식으로 풀어보기로 했다...

# 1 # 2 # 3 (2 + 1) # 5 (3 + 2) # 8 (5 + 3) # 13 (8 + 5) n = int(input()) if n == 1: print(1) elif n == 2: print(2) else: dp = [0]*(n+1) dp[1], dp[2] = 1, 2 for i in range(3,n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n]%10007) 이번 문제는 2xn 형태의 직사각형이 주어졌을 때, 2x1과 1x2 타일로 채울 수 있는 경우의 수를 구하는 문제이다. n=1, n=2, n=3 .. 인 경우의 수를 차례대로 구하다보니 dp[n] = dp[n-1] + dp[n-2] 라는 점화식을 도출해낼 수 있어서 쉽게 해결할 수 있었던 문제였다 :)

import sys input = sys.stdin.readline def fibo(n): if n == 0: print(1,0) return None if n == 1: print(0,1) return None dp = [[0]*2 for _ in range(n+1)] dp[0][0], dp[0][1] = 1,0 dp[1][0], dp[1][1] = 0,1 for i in range(2,n+1): dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] print(dp[n][0],dp[n][1]) t = int(input()) testcase = [0]*t for i in range(t): testcase[i] = int(input()..

# 1 3 6 10 # 1 2 3 4 def dynamic(data): floor = data[0] index = data[1] dp = [[0] * (index+1) for _ in range(floor+1)] for i in range(1,index+1): dp[0][i] = i for i in range(1,floor+1): for j in range(1, index+1): if j == 1: dp[i][j] = 1 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[floor][index] t = int(input()) data = [[0]*2 for _ in range(t)] for i in range(t): for j in range(2): data[i]..

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

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