WoohyunKing의 개발 성장일지

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

t = int(input()) result = [] for i in range(t): n, m = map(int,input().split()) input_data = list(map(int,input().split())) max_value = 0 array = [[0]*21 for _ in range(21)] dp = [[0]*21 for _ in range(21)] for i in range(n): for j in range(m): array[i][j] = input_data[(i*m)+j] for i in range(1,n+1): for j in range(1,m+1): if j == 1: dp[i][j] = array[i-1][j-1] for i in range(1,m+1): for j in ran..

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 부터 구하면서 점화식을 찾는 ..

first = list(input()) second = list(input()) first_len = len(first) second_len = len(second) dp = [[0]*(first_len+1) for _ in range(second_len+1)] for i in range(second_len): for j in range(first_len): if second[i] == first[j]: dp[i][j] = dp[i-1][j-1]+1 else: dp[i][j] = max(dp[i-1][j],dp[i][j-1]) print(dp[second_len-1][first_len-1]) 💡 LCS (Longest Common Subsequence)란? 2개 이상의 문자열에서에서 공통으로 나타나는 부..

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)

이번 문제는 이전에 풀었던 01타일 문제와 매우 유사한 문제로, 다음과 같은 조건을 만족하는 이친수의 개수를 구하는 문제이다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 이러한 패턴의 문제는 n=1 부터 차근차근 구하면서 점화식을 찾아내는 것이 핵심인데, n=1부터 차례대로 값을 구해본 결과 다음과 같은 점화식을 얻을 수 있었다. dp[1] = 1, d[2] = 1 dp[n] = dp[n-1] + dp[n-2] (n>=3) 이러한 점화식을 도출한 후, DP 테이블에 저장하여 쉽게 풀 수 있었던 DP 문제였다 :)

import sys input = sys.stdin.readline n = int(input()) data = list(map(int,input().split())) dp = [1]*n for i in range(1,n): for j in range(i): if data[i] < data[j]: dp[i] = max(dp[i],dp[j]+1) print(n - max(dp)) 이번 문제는 병사의 수 N과 각 병사의 전투력 정보를 입력받은 뒤, 모든 병사를 내림차 순으로 정렬하되 남아있는 병사의 수가 최대가 되도록 만드는 문제이다. 해당 문제는 이전에 풀이했던 LIS 문제와 상당히 유사한 문제인데, 문제에서 열외시키는 방법으로 수행한다는 말 때문에 쉽게 떠올리지 못한 것 같다. LIS 문제란 특정 조건을 ..

n = int(input()) array = list(map(int,input().split())) dp = [1]*n for i in range(n): for j in range(i): if array[i] > array[j]: dp[i] = max(dp[i], dp[j] + 1) print(max(dp)) 이번 문제는 주어진 수열에서, 증가하는 부분 수열 중에 가장 긴 부분 수열을 구하는 문제이다. 처음 이 문제를 풀 때는 값이 증가하는 경우와 값이 감소하는 경우를 나눠서 풀었었는데, 결국 틀리는 경우의 수가 많아서 이 방법은 포기하기로 하였다. 그래서 다른 분의 풀이를 참고해본 결과, 이 문제를 풀기 위한 핵심 아이디어는 다음과 같다. 먼저 초기에 모든 수들이 각자 가지는 길이는 1이므로 1차원 리..