백준 (223) 썸네일형 리스트형 [USACO] 백준 14165 - Team Building www.acmicpc.net/problem/14165 문제 소개 농부 존과 폴은 스테이트 페어에서 best in show라는 경쟁을 한다. 서로 가지고 있는 소들에게 점수를 부여하고 각 농부가 K마리의 소를 서로 점수가 높은 순으로 매칭하는데 한 진영의 소가 다른 진영의 소보다 모두 높은 점수로 매칭되면 이긴다. K가 주어지고 농부 존과 폴이 각각 N, M마리의 소를 가지고 있을 때 존이 이기는 경우의 수를 $10^9 + 9$로 나눈 모듈러를 출력해야 한다. 풀이 단순하게 존이 i번째 소, 폴이 j번째 소까지 각각 k마리를 뽑아서 존이 이기는 경우를 삼차원 동적계획법으로 풀 수 있다. (dp[i][j][k]) 다만 서로의 소를 매칭하는 경우를 일일이 탐색하면 시간복잡도는 $O(NM \times NMK)$.. [KOI] 백준 1866 - 택배 www.acmicpc.net/problem/1866 사전 지식 이 문제를 풀기 전에 USACO wifi setup과 BOJ 14400을 풀고 오는 것을 추천한다. 솔루션 - 편의점 2 / 솔루션 - wifi setup 풀이 트럭과 헬기를 적절히 써서 비용의 합을 최소로 해야한다. 비용의 최소는 wifi setup과 비슷하게 일차원 동적계획법으로 계산할 수 있다. 테이블의 정의는 dp[i] := i번째 지점까지 배송했을 때 비용의 최소 로 할 수 있으며 i번째 지점을 트럭으로 배송하거나 헬기로 어떤 지점에 물건을 나르고 그 지점에서 i번째 지점으로 트럭이 오는 경우로 나눠 계산하게 된다. 헬기로 배송한다고 했을 때 가장 이득을 보는 위치는 어떤 구간을 배송하기 위해 헬기를 이용할 때 그 구간의 중간 지점이.. 백준 2208 - 보석 줍기 www.acmicpc.net/problem/2208 풀이 배열의 prefix sum을 계산해준다. n개의 보석만큼 반복문을 돌리는데 다음 계산의 최댓값이 정답이 된다. 보석 i번째까지 전부 먹었을 때 누적합 - 이전 구간에서 최대로 손해를 입는 누적합 구현에서는 이전 구간에서 최대로 손해를 입는 누적합을 저장하기 위해 별도의 변수를 두었다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include using namespace std; int ar[100001]; int prefix[100001]; int n, m; int res; int main() { cin.tie(0); ios::sync_with.. 백준 15678 - 연세워터파크 www.acmicpc.net/problem/15678 단조 큐를 이용해 최적해를 빠른 속도로 계산할 수 있는 동적계획법 문제이다. 동적계획법에 단조 큐를 활용하는 과정은 다음과 같다. 1. 먼저 덱에서 현재 징검다리로 건너올 수 없는 징검다리를 모두 제거한다. 2. 지역 최적해를 가진 이전 징검다리에서 현재 징검다리로 건너올 경우의 최적해를 계산한다. 현재 징검다리를 시작점으로 해서 가지는 점수나 이전 징검다리에서 가지고 있는 최적해 + 현재 징검다리를 밟았을 때 점수 둘 중 하나가 될 것이다. 3. 계산한 최적해와 최대 점수를 비교해서 저장한다. #덱에는 이동할 수 있는 범위의 징검다리만 있으므로 계산한 최적해는 최댓값이 아닌 극댓값이라는 사실에 유의한다. 4. 현재 계산한 최적해보다 작은 값을 가지고.. 백준 17298 - 오큰수 www.acmicpc.net/problem/17298 오큰수를 더 쉽게 말하면 수열에 있는 어떤 수가 처음으로 만나는 자신보다 큰 수이다. 큰 수의 입장에서 생각해보자. 예를 들어 다음과 같은 수열이 있을 때 5 4 3 2 1 7 7을 제외한 모든 수의 오큰수는 7이 된다. 이를 잘 관찰하면 수열에서 어떤 수보다 왼쪽 방향으로 작은 수들은 모두 오큰수를 가질 수 있다는 것을 발견할 수 있다. 수열에 대해 반복문을 돌면서 while문을 이용해 스택에 마지막으로 올려진 항보다 현재 항이 크면 스택에 올려진 항을 pop하고 pop된 항의 오큰수를 현재 항으로 저장하면 수열의 모든 오큰수를 구할 수 있게 된다. 이렇게 오큰수를 모두 구한 뒤 출력해주면 정답을 받을 수 있다. 전체 코드 더보기 1 2 3 4 5 .. 이전 1 ··· 26 27 28 29 30 31 32 ··· 45 다음
