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