[BOJ] 백준 20553. 다오와 디지니의 데이트 (Gold II)

개인적으로 꽤 어렵게 느껴졌기 때문에 풀고난 후 티어를 보고 깜짝 놀랐다.

내가 정점/간선 인덱스를 헷갈리게 하는 유형에 약해서 그런진 모르겠지만, 나는 G1~P5 급이라 생각한다.

하지만 그만큼 배울점도 많았던 문제.

문제는 아래와 같다.

https://www.acmicpc.net/problem/20553

20553번: 다오와 디지니의 데이트

얘네 커플이었는지 이 문제땜에 첨 알았다...

얘들아 근데 너네 데이트는 어떻게 하니? 설마 카트 타면서 다 부수는건 아니지..?

---

의식의 흐름 및 해설

1번 마을에서 시작해서 반드시 1번 마을로 도착해야한다.

따라서 모든 길은 반드시 i번째 -> i+1번째 갈 때와 i+1번째 -> i번째 갈 때 거치게 되므로, 짝수번 거치게 된다.

즉, 그 길을 지나갈 때, 최소한 양 옆 장소의 만족도를 한번씩은 획득한 상태로 길을 건넌다는 것이다.

따라서 (i번째 - i+1번째) 길을 i번째 길이라고 하자.

 

5 11
0 6 -2 9 3
ans: 41

예제입력2를 예시로 들면,

d 배열은 [6, 4, 7, 12]가 되는데,

우리는 12를 얻는 길을 최대한 많이 거치는 것이 최적의 답을 얻을 수 있음을 알 수 있다.

따라서 그리디적으로 해결하면 되는데, 만족도 12를 얻는 길을 거치기 위해선, 그 전까지의 길들을 최소한 1번씩은 (돌아오는 것까지 포함하면 2번씩은) 거쳐야한다.

 

그러므로 d배열의 누적합인 p 배열을 만들어주자.

그 전까지의 길을 최소한 1번씩은 거치기 때문에, 거친 길의 양옆 만족도를 최소 1번씩은 얻을 것이다.

이제, 쭉 길을 탐색하면서 현재 위치한 길을 최대한 많이 거칠 때 최대값이 갱신되는지 체크해주면 된다.

 

주의할 점은, 현재 탐색중인 길이 T시간 이내에 탐색할 수 있는 길인지 체크해주어야한다.

탐색 가능하지도 않은 길인데, 탐색하고 있으면 안되기 때문!

---

테스트케이스

5 12
0 9 3 4 6
ans: 69

5 11
0 9 3 4 6
ans: 57

5 3
0 9 3 4 6
ans: 9

5 12
0 9 -2 6 -5
ans: 54

5 11
0 9 -2 6 -5
ans: 45

5 12
0 -1 2 3 -1
ans: 20

5 12
0 4 5 2 8
ans: 50

---

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=100011;
ll N,T,a[MAX],p[MAX],d[MAX],ans;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>N>>T;
	T/=2;
	for(int i=1;i<=N;i++)cin>>a[i];
	for(int i=1;i<N;i++){
		d[i]=a[i]+a[i+1];
		p[i]=p[i-1]+d[i];
	}
	for(int i=1;i<N;i++){
		if(i<=T)
			ans=max(ans, p[i-1]+d[i]*(T+1-i));
	}
	cout<<ans;
}

---

아무래도 그리디 문제다 보니, 해설을 참고하는 것 자체가 체감난이도를 많이 낮출 것이라 생각된다.

실제로 나도 지금 풀이를 쓰면서, 이 때 왜 이런 생각을 못했는지, 쓰고나니까 되게 쉽게 느껴진다고 생각이 들고 있으니 말이다.

 

따라서 지금 이 포스팅을 여기 밑쪽까지 보고 있다면, AC를 받았거나, 도저히 몰라서 풀이를 참고하는 경우라면 좋을 듯하다.

 

할로윈날 문제를 풀어 배경을 얻었다.

+)

할로윈에 1문제 이상 풀었더니 솔브드 배경을 획득했다.

개인적으로 저 캐릭터보단, 멋진 수학공식이나 할로윈 분장, 또는 수박과 같은 간지나는 배경이었으면 좋았을텐데 아쉽다.