BOJ 16765 Teamwork

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

16765번: Teamwork

문제 자체는 간단하지만, 이 문제를 풀 때 접근했던 방식이 앞으로 도움이 될 것 같아 포스팅 하게 되었다.

선 요약하면 다음과 같다.
1. 문제에 손이 안간다면, 좀 더 쉬운 문제로 바꿔서 생각해보자
2. 특정 값을 구하는 과정을 잘 이용해보자 ( 이 부분은 항상 잘 안됨 ) 

사실, 이 문제를 처음 풀 때 그룹의 소의 수가 무조건 K 인 줄 알았다. 
하여 점화식 DP[i] = max(DP[i-1]+arr[i], (max of arr [i] ~ arr[i-k+1]) * k + DP[i-k] ) 로 만들어 푸니 틀리댄다.

그런데 맞왜틀이라 생각하여 문제를 자세히 보니, "up to K " 라고 적혀있었다. 그룹의 소의 수가 1~K 개란 소리다.

따라서 앞서 구한 점화식의 K에 1~K 까지 대입하여  DP[i] 에 두면 된다.
DP[i] = max of arr [i] ~ arr[i-j+1]) * j + DP[i-j]  (j = 1 to k)
(j = 1 인 경우, DP[i-1] + arr[i] 가 되므로 해당 식으로 요약 가능하다)

만약 처음 점화식을 생각하지 못하고 계속 변화하는 K 에 대해 고려하면서 풀었다면, 좀 더 오래 결렸을 것이다.
하지만, 쉬운 문제로 치환하고 그것을 좀 더 일반적으로 푸는 과정에서 이 문제의 정해를 구할 수 있었다.

하지만 두번째 고민이 남아있었다. 어떻게 구간 i ~ i-k+1의 최대값을 각 loop 마다 구할 수 있냐였다.
만약 naive 하게 풀었다면, T(N,K) = O(NKK) 가 걸려 TLE 가 났을 것이다.

여기서 갑자기 생각난 것이, 구간 i ~ i + a 의 최대값은, 구간 i ~ i + a - 1 의 최대값과  i + a  중 큰 값을 선택하는 것이라는 것이 떠올랐다. 사실 당연한 것인데 그동안 무지성으로 max를 가져다 썼기 때문에 이를 떠올리는데 너무 시간이 오래 걸렸다.

해당 방법은 PS나 삼성 Expert 를 준비하면서 많이 접했던 방식인데, 너무 떠올리는게 늦는 것 같다.

하여 T(N,K) = O(NK) 로 줄여 문제를 해결할 수 있었다.

코드는 다음과 같다.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int n,m,k;
vector<int> arr;
vector<int> dp; //DP[i] = 1 ~ i 까지 구한 최대값


int main(){
    cin >> n >> k;
    arr.resize(n+1); dp.resize(n+1); 
    for(int i=1;i<=n;i++) cin >> arr[i];

    for(int i=1;i<=n;i++){
        m = arr[i];
        for(int j=1;j<=k && i-j >= 0;j++){
            dp[i] = max(dp[i], dp[i-j] + m*j);
            if(m < arr[i-j]) m = arr[i-j];
        }
    }
    cout << dp[n] << "\n";
    return 0;
}

PS. 해당 코드를 제출하고, 시간 최적화를 좀 해봤다. (vector -> int [], 입출력 함수 변경)
실험 결과 BOJ 상에서는 iostream 을 이용한 입출력이 cstdio를 이용한 입출력보다 메모리, 실행시간을 좀 더 많이 잡아먹는 것 같다.