https://www.acmicpc.net/problem/16765
16765번: Teamwork
In this example, the optimal solution is to group the first three cows and the last three cows, leaving the middle cow on a team by itself (remember that it is fine to have teams of size less than $K$). This effectively boosts the skill levels of the 7 cow
www.acmicpc.net
문제 자체는 간단하지만, 이 문제를 풀 때 접근했던 방식이 앞으로 도움이 될 것 같아 포스팅 하게 되었다.
선 요약하면 다음과 같다.
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를 이용한 입출력보다 메모리, 실행시간을 좀 더 많이 잡아먹는 것 같다.
'알고리즘' 카테고리의 다른 글
BOJ 15587 Cow at Large (Gold) (0) | 2023.05.14 |
---|---|
BOJ 14169 Laser and Mirrors (0) | 2023.03.02 |
BOJ 15749 Snow Boots (0) | 2022.10.10 |
BOJ 15750 Teleportation (0) | 2022.10.05 |
BOJ 15589 Lifeguards (Silver) (0) | 2022.09.28 |