BOJ 10564 - 팔굽혀펴기

* BOJ 10564 - 팔굽혀펴기

[분류 - 다이나믹 프로그래밍]

  처음엔 생각나는대로 풀었는데 시간과 메모리가 마음에 안들어서 계속 생각하다 문득 떠오른 풀이를 공유하고자 합니다.

[첫 풀이]

2차원 배열에서 dp[누적 회수][팀이 득점한 총 점수]로 설정해서 O(M N^2) 시간 복잡도를 갖는 풀이를 써봤습니다. 직관적이고 이해하기 쉬워서 작성은 금방했습니다만, 여러 테스트 케이스를 고려하면 "누적 회수"가 "팀이 득점한 총 점수"에 의존적으로 결정되기 때문에 N^2을 모두 채우지 않을거라는 기도 메타에 약 800ms으로 풀이가 맞았습니다.

[보다 확실하고 효율적인 풀이]

'이전 경기 결과에서 다음 경기에 점수 얼마를 얻었다'가 아니라 반대로 생각해봅시다. '첫 경기를 추가해보자'라고.

그러면 문제는 갑자기 단순해집니다. 가령 현재 세 번째 경기에서 팔굽혀펴기 회수가 10이고, 첫 경기를 7점으로 추가해봅시다. 그러면 총 네 번 경기해서 팔굽혀펴기 회수가 10 + 7 * 4 = 38로 바로 계산이 됩니다.

[경기 회수?] 네 이것이 바로 핵심입니다. 경기 회수를 고정해봅시다. 1회, 2회 그리고 3회 계속해서 n회까지 거듭하며 얻을 수 있는 점수를 다이나믹하게 계산해보는 겁니다. 예를 들어 5번째 경기 결과는 4번째 경기 결과에서 첫 경기를 추가해주는 방식입니다. 마찬가지로 11번째 경기 결과를 10번째 경기 결과에서 첫 경기를 추가해주는 겁니다. (이 아이디어는 https://www.acmicpc.net/problem/2419에서 가져왔습니다. 풀이 링크는 https://coloredrabbit.tistory.com/92)

[경기 회수의 최대값 L] 이건 간단하게 구할 수 있습니다. 경기 회수를 많이해서 N이 될 수 있으려면 S중 가장 최소 점수로 점수를 계속 득점해나갔다고 생각하면 됩니다. 최악의 경우에 이 값이 1일텐데 계속 1을 누계해서 N이 되려면 L(L+1)/2 = N의 방정식이 성립됩니다. 따라서 L의 최대값은 99입니다(100이면 100 * 101/2 = 5050이기에 N최대 초과).

[그래도 O(L M N^2)] 하나 더 생각해볼 것이 있어요. 바로 경기 회수에 대한 최소값 설정입니다. 만약 경기를 5번 했다고 가정해봅시다. 여기서 총 팔굽혀펴기 회수가 1이 될 수 있을까요? 절대 불가능합니다. S중 최소값을 minS라고 하면 적어도 minS * 5 * 6 / 2번을 해야하기 때문이죠. 따라서 경기 회수를 진행하면 진행할 수록 팔굽혀퍼기 회수의 최소값은 점점 커집니다. 이 최소값을 유지하면 수많은 가지를 쳐낼 수 있어요.

[참고 - 슬라이딩 윈도우] 경기 회수에 대해서 i번째 경기 회수를 한 경우는 i-1번째 경기 회수를 부분 문제로 두고 있습니다. 이 부분은 슬라이딩 윈도우로 메모리까지 아낄 수 있답니다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 5001, MAX_M = 10, INF = 1e9, L = 100;
int main() {
	int T, i, j, k, ans, N, M, S[MAX_M], t, minS, l, dp[2][MAX_N];
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &N, &M);
		memset(dp, 0xAF, sizeof dp);
		t = 0;
		for (minS = INF, i = 0; i < M; i++) {
			scanf("%d", &S[i]);
			minS = min(minS, S[i]);
		}
		dp[t][0] = 0;
		ans = l = 0, i = 1;
		while (l <= N) {
			memset(dp[!t], 0xAF, sizeof dp[!t]);
			for (j = l; j <= N; j++)
				for (k = 0; k < M; k++) if (j + S[k] * i <= N)
					dp[!t][j + S[k] * i] = max(dp[!t][j + S[k] * i], dp[t][j] + S[k]);
			ans = max(ans, dp[!t][N]);
			l += i * minS;
			i++, t = !t;
		}
		printf("%d\n", ans > 0 ? ans : -1);
	}
	return 0;
}