Algorithm 💡272 [백준 11052번] 카드 구매하기 n = int(input()) price = list(map(int,input().split())) dp = [[0]*(n+1) for _ in range(n+1)] for i in range(1,n+1): dp[i][1] = price[0]*i for i in range(2,n+1): for j in range(2,i+1): dp[i][j] = max(price[j-1]+dp[i-j][i-j],dp[i][j-1] ) print(dp[n][n]) 이번 문제는 구매하려고 하는 카드의 개수 N과 각 개수마다 구매하는데 필요한 비용 P1 ~ PN 까지 주어졌을 때, 카드 N개를 최대한 많은 비용으로 구매하였을 때의 금액을 구하는 문제이다. 이 문제를 풀 때 문득 '0-1 배낭 문제'가 떠올랐는데, 비슷한 느낌.. 2023. 3. 15. [백준 1010번] 다리놓기 def dynamic(data): n = data[0] m = data[1] dp = [[0]*(m+1) for _ in range(n+1)] for i in range(1,n+1): dp[i][i] = 1 for i in range(2,m+1): dp[1][i] = i for i in range(2, n+1): for j in range(i+1,m+1): dp[i][j] = dp[i-1][j-1] + dp[i][j-1] print(dp[n][m]) t = int(input()) testcase = [] for i in range(t): testcase.append(list(map(int,input().split()))) for i in testcase: dynamic(i) 이번 문제는 서쪽 사이트의 개.. 2023. 3. 15. [백준 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. 이전 1 ··· 32 33 34 35 36 37 38 ··· 46 다음
