[BOJ] 18186 라면 사기 (Large)
https://www.acmicpc.net/problem/18186
한 수열이 주어졌을 때, 해당 수열의 임의의 위치에서 {1}, {1, 1}, {1, 1, 1}를 여러 번 제거하여 해당 수열의 원소를 모두 0으로 만드는 문제. 단, 제거하는 비용은 문제에 주어진 규칙에 따라야 한다.
1/ 조건
1) 수열의 길이 N과 비용을 구성하는 숫자 B, C, 수열의 원소 A_i가 주어진다. 입력 제한은 다음과 같다:
● 3 ≤ N ≤ 10^6
● 1 ≤ B ≤ 10^6
● 1 ≤ C ≤ 10^6
● 0 ≤ A_i ≤ 10^6 (1 ≤ i ≤ N)
2) 수열의 제거 연산 - 즉 라면 구매는 다음과 같은 3가지의 방법만 존재한다:
(1) i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 B원이 든다.
(2) i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 (B+C)원이 든다.
(3) i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 (B+2C)원이 든다.
3) 최종적으로 모든 수열의 원소를 0으로 만들되, 최소 비용을 출력해야 한다.
4) 시간 제한은 1초, 메모리 제한은 64MB.
2/ 설계
1) 시간 제한을 보고 O(N^2)은 안 되겠다고 생각했다. 사실 순회 한 번에 끝내는 게 맞아보여서 DP 아니면 그리디겠구나 싶었다.
맨 처음 이미지는 쌓인 것을 덜어내는 이미지였다. 1을 덜어낼 것인지, 11을 덜어낼 것인지, 111을 덜어낼 것인지. 더 나아가서는 111...111을 덜어내는 것에 대해 생각했다. 하지만 32123처럼, 연속된 구간에서 1을 한 번 덜어내면 불연속구간(0)이 생겨버리는 경우에 대해서 잘 작동하기가 힘들었다. 다음 아이디어를 고려해야 했다.
2) 다음은 DP였다. a[i-1]까지는 전부 0으로 만들었다는 가정 하에 a[i], a[i+1], a[i+2]에서 뭘 얼마나 뺄 것인가가 중요했다. 가장 간단한 아이디어는 역시 001부터 111까지 총 7개의 가능성으로 분할하는 거였다. 개중에서 101과 010 001은 제외해야 했다. 어차피 칸을 움직이다 보면 a[i+1]을 새로운 a[i]로 여기는 시점이 올 테니, 010과 001은 의미가 없고, 101은 100과 001의 시너지 없는 합산이기 때문에 배제하는 게 옳았다. 나중 가서는 011도 비슷한 논리로 배제하는 게 옳다고 판단했다.
즉 100, 110, 111, 3가지만 남는다. 그냥 문제에서 제시한 자유도만 남은 것이다.
3) 그러면 상태를 어떻게 설정하는 게 좋을까? 이 부분에서 머리가 잘 안 돌아갔다. 아직 DP의 수양이 낮구나 하는 마음에 DP를 포기하고 그리디로 선회했다. 안되면 다시 DP로 돌아가겠다는 허섭한 마인드였다.
원점으로 돌아와서 생각했다. 결국 100과 110과 111의 중첩으로 문제를 해결해야 하는 건 맞다. 그런데 111의 가성비가 제일 좋다고 제일 먼저 111을 빼버리면 문제가 생기는 경우가 있었다. 1211이 그랬다. 1211 -> 0101 -> 0001 -> 0000의 순서보다 1211 -> 0111 -> 0000으로 가는 게 비용이 더 적다.
그러나 1121의 경우는 다르다. 111을 곧바로 빼버리는 게 더 이득이다. 나는 이 차이점이 정확히 어떤 지점에서 일어나는지 찾아내려고 애를 썼고 실패했다.
4) 그래서 결국 다른 사람들의 포스팅을 봤다. 코드를 보기 전에 한 대목이 스쳐지나가듯이 시야에 들어왔고, 감을 잡았다는 느낌에 바로 사이트를 껐다.
지금 와서 다시 재구성하기 때문에 당시의 생각과는 동떨어져 있긴 하지만, 그래도 서술하자면, 결국 1121과 1211의 차이를 집어내는 아주 간단한 가설로부터 시작해야 하는 게 맞다. 결국 i, i+1, i+2번째 인덱스 사이의 대소관계가 중요한 것이다. 나는 그것을 중점적으로 모든 경우의 수에 대해서 비교해봐야 했다. 어차피 몇 개 안 나오니까.
하여간, 결론적으로 a[i+1] > a[i+2]일 때 111을 우선시하면 불연속구간이 발생했다. 이게 문제였다. 그렇다면 이 부분에 대해서 해결을 해보자는 마음으로 일단 코드를 썼다.
3/ 구현
#include <stdio.h>
#define MAX_A_SIZE 1000002
#define MIN(a, b) ((a) < (b) ? (a) : (b))
long cost = 0;
int a[MAX_A_SIZE];
int n, b, c;
void
buy1(int i)
{
cost += (long) b * a[i];
a[i] = 0;
}
void
buy2(int i)
{
int min_val = MIN(a[i], a[i+1] - a[i+2]);
cost += (long) (b + c) * min_val;
a[i] -= min_val;
a[i+1] -= min_val;
}
void
buy3(int i)
{
int min_val = MIN(MIN(a[i], a[i+1]), a[i+2]);
cost += (long) (b + 2*c) * min_val;
a[i] -= min_val;
a[i+1] -= min_val;
a[i+2] -= min_val;
}
int
main()
{
scanf("%d %d %d", &n, &b, &c);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
a[n] = a[n+1] = 0;
if (b <= c) {
for (int i = 0; i < n; i++) {
cost += (long) a[i] * b;
}
} else {
for (int i = 0; i < n; i++) {
while (a[i] && a[i+1] > a[i+2]) {
buy2(i);
}
while (a[i] && a[i+1] && a[i+2]) {
buy3(i);
}
while (a[i]) {
buy1(i);
}
}
}
printf("%ld\n", cost);
return 0;
}
4/ 결과
5/ 후기
1) 다이아 치곤 쉽다는 이야기를 여러 번 들어서 도전했는데, 결국 혼자 힘으로는 해결하지 못했다. 그런데 돌아보면 정말 강제력이 있었다면 혼자 해냈을 법도 하다는 생각이 들어서 아쉬운 부분도 있었다. 그것까지 고려해서 다른 사람의 포스팅을 본 거긴 한데. 나는 한동안 쉬운 문제로 저점을 끌어올리는 게 좋다고 판단했고, 그게 취업을 위한 코딩 테스트에는 적합하다고 생각한다. 이제는 취업을 했고, 알고리즘 문제 해결은 그저 취미에 가까울 수밖에 없다. 딱 취미 수준에서, C나 C++를 공부한다는 생각으로 알고리즘 문제 해결을 지속할 생각이다. 목표는 다이아5 정도 될 것 같다. 앞으로는 좀 더 혼자 힘과 참고의 경계선에서 줄타기를 잘해보려 한다.
2) 사실 이 문제는 처음에 Python으로 풀었다. 저녁에 풀려는데 피곤한 상태에서 익숙지 않은 C언어로 문제를 푸려니 머리가 덜 돌아가는 느낌이라 일단 Python으로 풀고 오늘에야 C언어로 바꿔봤다. 별 차이는 없긴 한데ㅋㅋ C언어는 정말… 너무… 신기하다. 사내 스터디에서 공부하고 있는데 매일 신기하다. 어떻게 이럴 수가 있을까? 나는 언제쯤 신기해하지 않을까?
3) 예전에 'CP를 할 게 아니라면 알고리즘 문제 해결을 깊이 공부하는 데 의미가 있을까? 있다면 어떤 의미일까? 고민해볼 만한 거리인 것 같다.'라고 말한 적이 있었다. 여전히 고민 중이다. 예를 들어 persistent segment tree를 알아서 어디에 쓰지? convex hull trick 알아서 뭐함?? 같은 느낌으로... 사실 모르는 입장에서 함부로 입을 털면 안 되긴 한데. 일단 지적 자극이 있고, 시야가 넓어지기는 하고, 특정 언어를 (좁은 영역에서) 훈련할 수 있는데… 일단 해보려고 한다. 당장의 목표는 명료한 사전 설계와 빠른 구현이다.