백준 python 2565번 전깃줄 /11055번 수열 / 2156번 포도주 시식

백준 python 2565번 전깃줄

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

Python

n = int(input()) link = list() for _ in range(n):     link.append(tuple(map(int, input().split()))) link.sort(key=lambda x: x[0], reverse=True) dp = [1] * (link[0][0] + 1) def result():     for i in range(1, n):         a = link[i][0]         b = link[i][1]         max_value = 0         for j in range(i):             if b < link[j][1]:                 max_value = max(max_value, dp[link[j][0]])         dp[a] += max_value result() print(n - max(dp))

 

 

백준 python 11055번 가장 큰 증가 부분 수열

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

 

반응형

 

Python

n = int(input()) a = list(map(int, input().split())) dp = [0] * n def sequence():     dp[0] = a[0]     for i in range(1, n):         max_value = 0         for j in range(i):             if a[i] > a[j]:                 if abs(a[i] - a[j]) != 0:                     max_value = max(max_value, dp[j])         max_index = dp.index(max_value)         dp[i] = dp[max_index] + a[i] sequence() print(max(dp))

 

 

 

백준 2156번 포도주 시식

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

Python

n = int(input()) cost = [0] dp = [[0] * 3 for _ in range(n + 1)] for i in range(1, n + 1):     cost.append(int(input())) for i in range(3):     dp[1][i] = cost[1] def grape():     for i in range(2, n + 1):         for j in range(3):             if j == 0:                 temp = 0                 for k in range(1, 3):                     temp = max(temp, dp[i - 1][k])                 dp[i][j] = temp + cost[i]             elif j == 1:                 dp[i][j] = max(dp[i - 2]) + cost[i]             else:                 if i >= j + 1:                     dp[i][j] = max(dp[i - (j + 1)]) + cost[i] grape() result = 0 for i in range(n + 1):     result = max(result, max(dp[i])) print(result)