WoohyunKing의 개발 성장일지

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

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)을 초과하지..

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

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

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을 만들 수 있는 경우의 수를 구하는 문제이다. 문제..

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개의 카드를 구매하기 위해 지불해야 하는 금액..

n, k = map(int,input().split()) # 1차원 DP 테이블을 사용한 풀이 prices = [0] * n for i in range(n): prices[i] = int(input()) # dp[i] -> i원을 만들 때 가능한 경우의 수 dp = [0 for _ in range(k+1)] # dp[0] -> 0원을 만들 때 가능한 경우의 수, 동전을 사용하지 않는 경우 이므로 1로 초기화 dp[0] = 1 for price in prices: for i in range(price,k+1): dp[i] = dp[i] + dp[i-price] print(dp[k]) # 2차원 DP 테이블를 사용한 풀이(시간초과) # prices = [0] * (n+1) # for i in range(1,..

import sys sys.setrecursionlimit(50000000); m, n = map(int,input().split()) area = [list(map(int,input().split())) for _ in range(m)] dp = [[-1]*n for _ in range(m)] nx, ny = [-1,1,0,0], [0,0,-1,1] def dfs(x,y): # 도착 지점에 도달하면 1 리턴 if x == (m-1) and y == (n-1): return 1 # 이미 방문한 길이라면 경우의 수를 구하지 않고 해당 위치에서 출발하는 경우의 수 리턴 if dp[x][y] != -1: return dp[x][y] way_count = 0 for i in range(4): temp_x = x..

n = int(input()) data = [] dp = [1]*n for _ in range(n): data.append(list(map(int,input().split()))) data.sort(key=lambda x:x[0]) for i in range(1,n): for j in range(i): if data[i][1] > data[j][1]: dp[i] = max(dp[i], dp[j]+1) print(n-max(dp)) 이번 문제는 A와 B 전봇대 사이에 연결된 전깃줄의 정보와 전깃줄의 개수가 주어졌을 때, 모든 전깃줄이 서로 교차하지 않도록 하기 위해 제거해야 하는 전깃줄의 최소 개수를 구하는 문제이다. 처음에 이 문제를 접했을 때 이전에 풀던 DP 방식(n=1 부터 구하면서 점화식을 찾는 ..

n = int(input()) data = [] for i in range(n): data.append(tuple(map(int,input().split()))) dp = [0] * 1006 for i in range(n-1,-1,-1): time = data[i][0] value = data[i][1] if (i+time)