취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28071번 문제인 승형이의 사탕 사기이다.
문제는 아래 링크를 확인하자.

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

N종류의 사탕상자를 차례대로 읽어나갈 때, dp[m][k]를 이전까지 읽은 사탕상자들을 총 m개 사용해 얻을 수 있는 사탕의 개수 중 K로 나눈 나머지가 k인 값의 최댓값으로 정의하자.

이 때, 새로운 사탕상자의 크기 n을 읽어들였을 때, dp[m][k]를 m이 작은 순서대로 찾아가 각 사탕 개수에 n개의 사탕을 추가해 만들 수 있는 새로운 사탕개수의 값을 이용해 dp[m+1][k'](k'은 새 사탕개수를 K로 나눈 나머지)의 값을 갱신해나가는 것으로 dp배열을 올바르게 갱신해나갈 수 있다. 각 상태에 여러 사탕상자가 아닌 하나의 사탕상자만을 추가해보는 것으로 충분한 이유는 이후에 dp[m+1][k'] 상태에 대하여 다시 사탕상자를 하나 추가해보는 것을 시도하기 때문이다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, M, K;
int dp[301][301]; // dp[상자m개][K로 나눈 나머지]: 해당 조건 만족하는 사탕 최댓값

int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> K;
	for (int m = 0; m <= M; m++) {
		for (int k = 0; k < K; k++) {
			dp[m][k] = -1000000007;
		}
	}
	dp[0][0] = 0;

	while (N--) {
		int x; cin >> x;
		for (int m = 0; m < M; m++) {
			for (int k = 0; k < K; k++) {
				int tmp = dp[m][k] + x;
				dp[m + 1][tmp % K] = max(dp[m + 1][tmp % K], tmp);
			}
		}
	}

	for (int m = 1; m <= M; m++) ans = max(ans, dp[m][0]);

	cout << ans;
}