본문 바로가기

DP

 (17)
창영이와 점프[백준 22114] https://www.acmicpc.net/problem/22114 두 포인터를 사용해서 해결하면 된다. n, k = map(int, input().split())arr = list(map(int, input().split()))l, ans, j = 0, 0, 0for r in range(n - 1): if arr[r] > k: j += 1 while j > 1: if arr[l] > k: # 점프 복구 j -= 1 l += 1 ans = max(ans, r - l + 1 + 1) print(ans)
The Bale Tower [백준 6221] https://www.acmicpc.net/problem/6221  n = int(input())bales = []for _ in range(n): width, breadth = map(int, input().split()) bales.append((width, breadth))bales.sort(key=lambda x: (x[0], x[1]))dp = [1] * n for i in range(n): for j in range(i): if bales[j][0]
가장 긴 짝수 연속한 부분 수열 (small) [백준 22857] https://www.acmicpc.net/problem/22857 두 포인터를 사용해서 문제 해결을 하면 된다. def find(N, K, S): l = 0 max_length = 0 removed = 0 # 현재 구간 [l..r] 안의 홀수 개수 for r in range(N): if S[r] % 2 != 0: removed += 1 while removed > K: if S[l] % 2 != 0: removed -= 1 l += 1 sub = (r - l + 1) - removed max_length = max(max_length, sub) ..
회의실 배정3[백준 19622] https://www.acmicpc.net/problem/19622 이전 문제인 회의실 배정 2랑 같은 방법으로 풀면 된다. n = int(input())arr= []for i in range(n): a,b,c = map(int , input().split()) arr.append((a,b,c))arr.sort(key = lambda x : x[1])dp = [0 for _ in range(n)] dp[0] = arr[0][2]for i in range(1,n): dp[i] = dp[i-1] for j in range(i-1 , -1,-1): if arr[j][1]
가장 큰 감소 부분 수열[백준 17216] https://www.acmicpc.net/problem/17216 n = int(input())arr = list(map(int, input().split()))dp = [0 for _ in range(n)]dp[0] = arr[0] # arr = 9 2 1 100 22# dp = 9 11 12 100 122for i in range(1, n): dp[i] =arr[i] cnt = 0 for j in range(i-1 , -1,-1): if arr[i]
회의실 배정2 [백준 19621] https://www.acmicpc.net/problem/19621 배낭문제랑 비슷한 방법으로 문제 해결 하면 된다. n = int(input())# 회의 정보를 담을 리스트array = []for _ in range(n): array.append(list(map(int, input().split())))array.sort(key=lambda x: x[1])# DP 배열 초기화dp = [0] * ndp[0] = array[0][2]for i in range(1, n): dp[i] = dp[i - 1] for j in range(i - 1, -1, -1): if array[j][1]
무한 수열[백준 1351] https://www.acmicpc.net/problem/1351 def dpq(n, p, q, memo): if n == 0: return 1 if n in memo: return memo[n] pid = n // p qid = n // q memo[n] = dpq(pid, p, q, memo) + dpq(qid, p, q, memo) return memo[n]n, p, q = map(int, input().split())memo = {}print(dpq(n, p, q, memo))print(memo)
극장 좌석( 백준 2302) https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net import sys input = sys.stdin.readline n =int(input()) m = int(input()) ans = 1 fixed =[] dp=[0]*(42) dp[0] = 1 dp[1] = 1 dp[2] = 2 for i in range(3, len(dp)): dp[i] = dp[i-1]+dp[i-2] for i in range(m): k = int(input()) fixed.appen..

티스토리툴바