문제 링크 : www.acmicpc.net/problem/19857
문제 풀이
이 문제를 딱 보고나서, 당연히 이 문제는 greedy or DP 느낌의 문제라고 생각이 들었다. 하지만 조금 더 고민을 해보니 DP라고 할 만한 요소가 하나도 존재하지 않다는 것을 깨달았다. 그리고 나서는 '만들 수 있는 최댓값'이라는 단어에 집중을 했고, 어떤 값이 만들 수 있는지 판별하는 것이 훨씬 쉬울 것 같아 파라메트릭 서치를 쓰는 방향으로 설정하였다.
마지막에 광물 i를 남길 수 있을까? 직접 i를 역추적 해보면서 생각하였다. 어떤 광물 j를 만들기 위해서는 0~j-1가 하나씩 존재하면 된다. j 보다 큰 광물은 하나도 쓸모가 없다. j이상의 광물을 가장 잘 쓰는 방법은 그 광물 하나로 0짜리 광물 하나는 만드는 것이다. 0짜리 광물은 1이상의 모든 광물을 만드는데 사용되어진다.
이제 위에서 관찰한 사실을 가지고 greedy하게 판별을 하면 된다. i에 대해서 확인하려고 할 때 i에서 0까지 다음과 같은 행동을 하면 된다.
1. i이상의 모든 광물은 0광물로 바꾼다.
2. 0부터 i-1까지의 모든 광물은 1개씩 필요하다.
3. i-1부터 내려가면서 0까지 탐색을 하자. 이때 현재 확인하는 값이 x라고 하자.
3-1. 광물 x의 수가 필요한 광물 x의 수보다 적은 경우, 적은 만큼 0~x-1의 광물이 필요하게 된다.
3-2. 광물 x의 수가 필요한 광물 x의 수보다 많은 경우, 남는 만큼 0광물로 바꾼다.
4. 0까지 내려오면, 필요한 0 광물의 수와, 0으로 바꾼 광물을 합쳐서 총 0광물의 개수를 비교하여, 가지고 있는게 더 많으면 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll arr[1010101];
int main(){
ll i,j,k,l,m,n,all=0;
scanf("%lld",&n);
for(i=0;i<n;i++){
scanf("%lld",&arr[i]);
all+=arr[i];
}
if(all==1){
ll ans=1;
for(i=0;i<=101010;i++)
if(arr[i])
ans=max(ans,i);
printf("%lld",ans);
return 0;
}
ll lo=0;
ll hi=200000;
ll mid;
while(lo<hi){
mid=(lo+hi)/2;
ll st=1;
ll nam=0;
for(i=mid;i<=n;i++)
nam+=arr[i];
for(i=mid-1;i>=1;i--){
if(st<=arr[i]) nam+=arr[i]-st;
else st+=(st-arr[i]);
st=min(st,(ll)1e17);
}
if(nam+arr[0]>=st) lo=mid+1;
else hi=mid;
}
printf("%lld\n",lo-1);
}
|
cs |