DynamicProgramming32 [백준 2096번] 내려가기 https://www.acmicpc.net/problem/2096import sysinput = sys.stdin.readlinen = int(input())dp_max = [0]*3dp_min = [0]*3for _ in range(n): a, b, c = map(int,input().split()) temp_max = dp_max[:] temp_min = dp_min[:] for i in range(3): if i == 0: dp_max[i] = a + max(temp_max[0],temp_max[1]) dp_min[i] = a + min(temp_min[0],temp_min[1]) elif i == 1: .. 2024. 6. 28. [HackerRank] Knapsack def unboundedKnapsack(k, arr): # Write your code here row = len(arr) col = k dp = [[0]*(k+1) for _ in range(row+1)] for i in range(1,row+1): dp[i][0] = 1 for i in range(1,row+1): for j in range(1,col+1): if j >= arr[i-1]: dp[i][j] = dp[i-1][j] + dp[i][j-arr[i-1]] else: dp[i][j] = dp[i-1][j] for i in range(col,-1,-1): if dp[row][i] != 0: return i 이번 문제는 주어진 배열(arr)의 원소들을 가지고 만들 수 있는 타겟 값(k)을 초과하지.. 2023. 5. 20. [HackerRank] Sherlock and Cost def cost(B): # Write your code here length = len(B) dp = [[0]*2 for _ in range(length)] for i in range(1,length): # A[i] == B[i]인 경우 dp[i][0] = max(abs(B[i]-B[i-1])+dp[i-1][0], abs(B[i]-1)+dp[i-1][1]) # A[i] == 1인 경우 dp[i][1] = max(abs(1-B[i-1])+dp[i-1][0], dp[i-1][1] ) return max(dp[length-1]) 이번 문제는 자연수 배열 B가 주어질 때, 이 B로부터 새로운 배열 A를 정의할 때 모든 배열의 원소 A[i]는 1 2023. 5. 15. [HackerRank] The Maximum Subarray def maxSubarray(arr): # Write your code here len_arr = len(arr) dp_array = [0]*(len_arr) dp_sequence = [0]*(len_arr) dp_array[0], dp_sequence[0] = arr[0], arr[0] for i in range(1,len_arr): dp_array[i] = max(arr[i], arr[i]+dp_array[i-1]) for i in range(1,len_arr): dp_sequence[i] = max(dp_sequence[i-1], dp_sequence[i-1]+arr[i], arr[i]) return [max(dp_array),dp_sequence[len_arr-1]] 이번 문제는 주어진 배열(ar.. 2023. 5. 15. [HackerRank] The Coin Change Problem def getWays(n, c): # Write your code here coin_count = len(c) dp = [[0]*(n+1) for _ in range(coin_count+1)] for i in range(1,coin_count+1): dp[i][0] = 1 for i in range(1,coin_count+1): for j in range(1,n+1): coin_value = c[i-1] if coin_value > j : dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i][j-coin_value] return dp[coin_count][n] 이번 문제는 주어진 c 배열 안의 값들로 n을 만들 수 있는 경우의 수를 구하는 문제이다. 문제.. 2023. 5. 14. [백준 16194번] 카드 구매하기 2 n = int(input()) data = list(map(int,input().split())) p_count = len(data) dp = [[0]*(n+1) for _ in range(p_count+1)] for i in range(1,n+1): dp[1][i] = data[0]*i for i in range(2,p_count+1): for j in range(1,n+1): if i > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = min(dp[i-1][j], data[i-1] + dp[i][j-i]) print(dp[p_count][n]) 이번 문제는 P1부터 PN까지 카드가 N개가 포함된 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 지불해야 하는 금액.. 2023. 5. 4. 이전 1 2 3 4 ··· 6 다음
