[알고리즘 문제] 31063번 - Candy Cane Feast

출처 : https://www.acmicpc.net/problem/31063

 

해당 문제는 풀이가 굉장히 짧기에 포스팅이 짧지만, 교훈이 매우 중요할 것 같습니다.

 

1. 접근 과정

 

문제를 대충 보아하니 O(NM) 으로 TLE가 발생할 것 같다는 느낌이 든다. 따라서 어떤 알고리즘을 사용해서, 어떤 아이디어를 사용해서 최적화할 수 있을까? 를 관점으로 계속 생각하였다. 

 

이전에 포스팅했던 SegmentTree 중 Lazy 하지 않더라도 연산 횟수가 제한된 경우의 문제를 떠올리며 입력의 최댓값을 보아하니 가망이 없겠구나... 싶었다.

 

long long 타입까지 가능성이 있기에 고민하던 중 2^63 이라는 숫자 중 지수 부분을 활용하고자 생각하였고 문제 메커니즘을 다시 살펴보니 맨 앞의 소는 항상 먹을 수 밖에 없으며 다 먹거나 일부만 먹는 2가지로 나눌 수 있었다. 

 

맨 앞의 소가 남긴다면 자신의 키 만큼 먹었다는 뜻이며 키가 2배가 된다. 반대로 다 먹는다면 먹은만큼 성장하고 끝낸다. 

따라서 실제로는 O(NM) 이 아니라 O( max(M, log10e9) ) 인 셈이었다. 

 

따라서 위에서 시키는 그대로 구현하고 다 먹은 경우에 break 하는 구문을 추가해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int N, M;
long long C[200005], H[200005];

int main()
{
    ios_base::sync_with_stdio(0);
    cin>>N>>M;
    for(int i=1;i<=N;i++) cin>>C[i];
    for(int i=1;i<=M;i++) cin>>H[i];
    for(int i=1;i<=M;i++){
        long long int max_c = 0;
        for(int j=1; j<=N;j++){
            if(H[i]<=0) break;
            long long temp=min(max(C[j]-max_c, 0LL),H[i]);
            max_c=max(max_c, C[j]), C[j]+=temp, H[i]-=temp;
        }
    }
    for(int i=1;i<=N;i++) cout<<C[i]<<"\n";
}

 

---

 

교훈

이전까지 문제를 보고 N^2은 안되니 NlogN 로 하고.. 어떤 알고리즘을 쓸까.. 어떻게 최적화할까... 고민했습니다. 다시 말하자면 여태까지 "탑다운" 처럼 알고리즘을 "선택"하고 문제에서 요구하는 것을 구하기 위해 추가할 것들을 생각하기에 활용 문제에서 허덕였습니다.

 

물론 고수분들은 바로 "이 알고리즘" 하고 답이 보일 수도 있지만 아직 저에게는 이른 것 같습니다.  제가 하고싶은 예기는 알고리즘을 사용할 때 문제 상황과 요구하는 메커니즘을 이해하고, 타당한 이유를 가지고 선택해야 한다는 말입니다. 즉 바텀업 방식이죠! 

 

중요한 것은 문제의 메커니즘과 특징, 문제를 해결하기 위한 정보와 이를 얻기 위한 자료구조 활용

 

 

따라서 저는 위 글을 토대로 앞으로 문제를 다른 방법으로 접근해 봐야할 것 같습니다... 여러분들은 어떻게 생각하시나요?