본문 바로가기

Algorithm 💡/DP41

[백준 1912번] 연속합 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 테이블에 저장해가는 방식으로 풀어보기로 했다... 2023. 3. 14.
[백준 11726번] 2xn 타일링 # 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] 라는 점화식을 도출해낼 수 있어서 쉽게 해결할 수 있었던 문제였다 :) 2023. 3. 14.
[백준 1003번] 피보나치 함수 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().. 2023. 3. 13.
[백준 2775번] 부녀회장이 될테야 # 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].. 2023. 3. 13.
[백준 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.

티스토리툴바