라면 사기 시리즈
다이아 문제 중 푼 사람이 젤 많은 문제들이다.
이번에 랜덤 마라톤 풀다가 본 그리디랑 비슷한 느낌으로 접근했고
질문 게시판들에 있는 반례들과 질문 글들을 읽어보며 풀 수 있었다.
출제자의 증명 글은 밑에 있는데 간단하면서도 떠올리기 많이 힘든(나는 불가능..?) 아이디어이다.
그럼에도 이런 접근 방법이 있다는 것을 알고 다음에는 응용을 할 수 있을 것이다.
large가 더 큰 범위를 가지기도 하고, 선형으로 반드시 풀어야한다는 힌트도 되기에 large를 기준으로 풀이를 적었다.
우선 문제를 봤을 때 a<=b면 a로 전부 사는 것이 당연하므로 넘어가고 a>b일 때만 고려하면
1개와 2개를 사는 경우만 있다면 가능하다면 2개를 사는 것이 이득임이 확실하다.
그렇다면 2개와 3개를 살 수 있는 경우에서 무엇을 사는 것이 이득일까를 생각해봤는데
기본적으로는 3개를 사는 것이 이득이지 않을까 싶었는데
1
1 2 1 1
과 같은 예제에서는 2개씩 살 수 있는 만큼 최대한 채우는 것이 필요하다.
2개, 2개, 1개는 2a+3b이지만 3개, 1개, 1개는 3a+2b가 되기 때문이다.
그래서 케이스를 나눠서 생각을 해보기로 했는데 우선 현재를 v[i]라고 했을 때 v[i+1]이 0이라면
연속해서 살 수 없으므로 1개씩 사야한다.
다음 v[i]>v[i+1]이라면 v[i]에서 2개를 사던 3개를 사던 v[i]-v[i+1]개는 1개씩 사야하는 운명이다.
그러므로 v[i]-v[i-1]개 만큼을 1개씩 사주고 v[i]=v[i+1]로 만들어줬다.
그러면 이제 v[i]<=v[i+1]인 상태일 것이고 v[i+2]와 비교를 해본다.
우선 v[i]<=v[i+1]<=v[i+2]와 같은 증가하는 상태라면 v[i]번 3개씩 사는 것이 가장 이득이다.
v[i]=0이 되고 다시 v[i+1]부터 위의 과정을 반복한다.
하지만 v[i]<=v[i+1]이면서 v[i+1]>v[i+2]라면 v[i]에서 2개씩 사면서 위 형태의 증가 수열로 만들어줘야 한다.
그래서 min(v[i], v[i+1]-v[i+2])만큼 2개씩 빼주면 v[i]<=v[i+1]<=v[i+2]가 되고, 위의 분기점으로 갈 것이다.
출제자 풀이
사실 보고도 그런가?? 싶긴 한데 각 라면마다 B, C, D로 마킹을 한다고 생각하고
B의 의미는 비용 B로 구매했다, C의 의미는 전칸에 있는 B라면과 묶였음
D의 의미는 전전칸에 있는 B와 전칸에 있는 C와 묶어서 적었다는 것이 된다.
구매 비용이 최소가 되려면 B를 적는 것이 최소가 되어야하는 것은 당연하다.
이제 알파벳을 적는데, C는 i번째의 B를 이용해서 i+1번째 적는 것이고
D는 i번째의 C를 이용해서 i+1번째 적는 것이다. 남는 것에는 B가 적힌다.
그렇기에 2개로 채울 수 있는 것을 전부 채운 다음(C를 쓰기)
C를 이용해서 D를 적을 수 있다면 최대한 해주고, 남은 자리에 B를 적어주면 된다고 한다.
어렵네..
라면 사기 large 푼 코드이다.
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#define ll long long
#define i128 __int128_t
#include <bits/stdc++.h>
using namespace std;
long long n, m, t, k = 0;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 998'244'353;
using P=pair<ll,ll>;
long long a, b, c, d;
long long ans = 0;
cin >> n >> a >> b;
vector<ll> v(n+2, 0);
//a
//a+b
//a+2*b로 변경
ll tt=0;
for(int i=0;i<n;i++)cin>>v[i];
if(a<=b){ //이러면 하나짜리 다 사고
for(int i=0;i<n;i++)tt+=v[i];
ans=tt*a;
cout << ans;
return 0;
}
for(int i=0;i<n;i++){
ll tmp;
while(v[i]>0){
if(v[i+1]>0){
if(v[i+2]>0){
if(v[i]>v[i+1]){ //앞이 뒤보다 크면 1개를 사야만 하는 듯?
ans+=(v[i]-v[i+1])*a;
v[i]=v[i+1];
}
else{ //이제 처음이랑 두번째는 같거나 앞에가 더 작고
if(v[i+1]>v[i+2]){ // 1 3 2 느낌이거나 3 3 2 느낌이겠죠
tmp=min(v[i], v[i+1]-v[i+2]); // 이만큼을 2개씩 빼면
ans+=tmp*(a+b);
v[i]-=tmp;
v[i+1]-=tmp;
}
else{ //증가 수열이면?
tmp=v[i];
ans+=(a+2*b)*tmp;
v[i]-=tmp;
v[i+1]-=tmp;
v[i+2]-=tmp;
}
}
}
else{
tmp=min(v[i], v[i+1]); //2개만 있을 때
ans+=tmp*(a+b);
v[i]-=tmp;
v[i+1]-=tmp;
}
}
else{
ans+=v[i]*a; // 1개만 덜렁 있을 때
v[i]=0;
}
}
}
cout << ans;
return 0;
}