-
백준 16238: 독수리코딩 2022. 3. 9. 14:17
https://www.acmicpc.net/problem/16238
풀이
물론 문제 조건에서는 왼쪽 또는 오른쪽에서 날기 시작할 수 있다고 했지만, 사실 관찰을 해보면
왼쪽에서만 날기 시작해도 정답에 영향을 주지 않습니다. 즉, 정해가 왼쪽과 오른쪽에서 날기 시작하는 것이 섞여있는 것이라면 그 위치들을 오름차순 정렬하여 순서대로 먹는 것도 같은 결과를 보여줍니다. 증명은 쉬우므로 생략하겠습니다.
위의 관찰을 하면 쉽게 dp로 풀 수 있습니다(기여창을 보니 먹는 위치의 개수를 고정시키고 정렬하여 그리디로 하면 된다고도 합니다). $dp[x][t]=($시간이 $t$만큼 지났고, 현재 $x-1$까지의 위치에 남은 양이 모두 $0$마리일 때 먹을 수 있는 최대 양의 수$)$라고 정의합니다. 그렇다면 약간의 케이스를 추가해서 점화식을 세웁니다.
1. $a[x]\leq t$일 때, $dp[x][t]=dp[x+1][t]$로 구할 수 있습니다(위치 $x$의 양이 없으므로 먹을 수 없습니다).
2. $a[x]>t$일 때, $dp[x][t]=\mathrm{max}(dp[x+1][t],\ dp[x+1][t+1]+a[x]-t)$로 구할 수 있습니다(위치 $x$의 양을 먹을지 안 먹을지 이득이 되는 경우를 선택합니다).
코드
더보기#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n, a[1001], dp[1001][1001]; ll dfs(int x, ll t) { if(x>=n) return 0; if(dp[x][t]>-1) return dp[x][t]; dp[x][t]=dfs(x+1, t); if(a[x]<=t) return dp[x][t]; dp[x][t]=max(dfs(x+1, t+1)+a[x]-t, dp[x][t]); return dp[x][t]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; memset(dp, -1, sizeof(dp)); for(int i=0; i<n; i++) cin >> a[i]; cout << dfs(0, 0); }
'코딩' 카테고리의 다른 글
CodeTON Round 1 (Div. 1 + Div. 2) (0) 2022.03.26 백준 20106: Cave (0) 2022.02.23 백준 20085: Detecting Molecules (1) 2022.02.22 백준 21761: 초직사각형 (3) 2022.01.28 백준 1115: 순열 (0) 2022.01.13