Coding Test/DP
[1231] 주식왕 동호 (냅색 알고리즘)
1231번: 주식왕 동호 첫 줄에는 주식의 개수 C(1 ≤ C ≤ 50)과 주식 매입 및 매각을 할 기간 D(2 ≤ D ≤ 10), 초기 자금 M(1 ≤ M ≤ 200,000)이 공백으로 구분되어 주어진다. 두 번째 줄부터 C+1번째 줄까지 각 줄에는 각각 주 www.acmicpc.net 분석 [12865] 평범한 배낭 (냅색 알고리즘) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 karla.tistory.com 풀이 import sys input=sys.stdin.readline c,d,m=map(int..
[7570] 줄세우기 (연속 최장 증가 수열, LIS)
7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 분석 유사문제 : 2631 [2631] 줄 세우기 (2중 for문) 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과 karla.tistory.com 추가 조건 : 이동하는 어린이를 제일 앞이나 제일 뒤로만 보낼 수 있음 ➔ 바로 옆에 있는 최장 증가 수열을 구해야함 4 2 3 1 5 1. 한 명의 어린이를 뽑아서 원하는 곳..
[2631] 줄 세우기 (최장증가수열, LIS, 이분 탐색)
2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 분석 정렬되어 있는 어린이 빼고 나머지를 이동하므로 LIS의 길이를 구한 뒤 N에서 뺌 풀이 import sys from bisect import bisect_left input=sys.stdin.readline n = int(input()) arr=[] for _ in range(n): arr.append(int(input())) d=[] for i in arr: k = bisect_left(d, i) if len(d) == k: d+=[i] else: d[k]=i ..
[2631] 줄 세우기 (최장증가수열, LIS, 2중 for문)
2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 분석 정렬되어 있는 어린이 빼고 나머지를 이동하므로 LIS의 길이를 구한 뒤 N에서 뺌 풀이 import sys input=sys.stdin.readline n = int(input()) arr=[] for _ in range(n): arr.append(int(input())) dp = [0 for _ in range(n)] for i in range(n): dp[i] = 1 for j in range(i): if arr[j] < arr[i]: dp[i] = max(d..
[11053] 가장 긴 증가하는 부분수열 (LIS)
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 분석 1 ≤ N ≤ 1,000 1 ≤ Ai ≤ 1,000 풀이 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) dp = [1]*n for i in range(1,n): for j in range(i): if arr[i] > arr[j]: dp[i] = max(dp[i],..
[2294] 동전 2 (동전 개수 최소값)
2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 분석 동전 교환 (DP) 분석 더보기 karla.tistory.com 풀이 """ n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 ..
[2293] 동전 1 (경우의 수 구하기)
2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 분석 [2624] 동전 바꿔주기 (DP) 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방 karla.tistory.com 풀이 """ n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각..
[12865] 평범한 배낭 (냅색 알고리즘)
12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 분석 가방에 최대 Mkg 까지 담을 수 있을 때, dp[i][j] = 가방에 담은 물건의 무게 합이 i일 때, 처음 j개의 물건 중 담을 수 있는 최대 가치 ( 1 < i