본문 바로가기

Algorithm 💡/DP41

[백준 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.
[백준 2293번] 동전1 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,.. 2023. 4. 11.
[백준 1520번] 내리막 길 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.. 2023. 4. 10.
[이코테] 금광 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.. 2023. 3. 27.
[백준 2565번] 전깃줄 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 부터 구하면서 점화식을 찾는 .. 2023. 3. 25.
[백준 9251번] LCS 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개 이상의 문자열에서에서 공통으로 나타나는 부.. 2023. 3. 23.

티스토리툴바