본문 바로가기
반응형

Problem Solving/Dynamic Programming20

[다이나믹 프로그래밍] 백준 7579번 : 앱 / 골드 3 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net import sys input = sys.stdin.readline n, capacity = map(int, input().split()) byte = list(map(int, input().split())) cost = list(map(int, input().split())) max_cost = sum(cost) dp = [[0]*(max_cost+1) for _ in range(n+1)] for i .. 2021. 8. 22.
[다이나믹 프로그래밍] 백준 17404번: RGB거리 2 / 골드 4** https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) dp = [[0, 0, 0] for _ in range(n)] colors = [[0, 0, 0] for _ in range(n)] for i in range(n): colors[i] = list(map(int, input().split())) dp[0] = colors[.. 2021. 8. 19.
[다이나믹 프로그래밍] 백준 9252번 : LCS 2 / 골드 5 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net a = input() b = input() dp = [[0]*(len(b)+1) for _ in range(len(a)+1)] for i in range(1, len(a)+1): for j in range(1, len(b)+1): if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1]+1 else: dp[i][j] = max.. 2021. 8. 15.
[다이나믹 프로그래밍] 백준 2096번: 내려가기 / 골드 4 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net import sys n = int(sys.stdin.readline()) max_dp = list(map(int, sys.stdin.readline().split())) min_dp = max_dp for i in range(1, n): a, b, c = map(int, sys.stdin.readline().split()) na1 = a + max(max_dp[0], max_dp[1]) nb1 = b + max.. 2021. 8. 13.
[다이나믹 프로그래밍] 백준 9251번: LCS / 골드 5 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net str1 = input() str2 = input() dp = [[0]*(len(str1)+1) for x in range(len(str2)+1)] for i in range(1, len(str2)+1): for j in range(1, len(str1)+1): if str1[j-1] == str2[i-1]: dp[i][j] = dp[i-1][j-1]+.. 2021. 7. 23.
[다이나믹 프로그래밍] 백준 1932번: 정수 삼각형 https://www.acmicpc.net/problem/1932 그리디로 생각하기 쉽지만 dp문제이다. 매번 큰수를 택하는 식으로 접근하면(그리디) 문제가 풀리지 않는다. n = int(input()) triangle=[] for i in range(n): triangle.append(list(map(int,input().split()))) dp =[triangle[0][0]] for i in range(1,n): # i means depth ndp = [] for j in range(i+1): if j==0 : # left edge pre = dp[j] elif j==i: # right edge pre = dp[j-1] else: pre = max(dp[j-1], dp[j]) ndp.append(pr.. 2021. 5. 27.
반응형

티스토리툴바