취미로 코딩하기

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

이번에 볼 문제는 백준 26936번 문제인 Gourmeten이다.
문제는 아래 링크를 확인하자.

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

정확히 i분동안 식사를 하는 각 방법은 마지막에 먹은 음식이 무엇이냐에 따라 총 N가지로 나누어 생각할 수 있다.

위의 관찰을 이용하면 정확히 i분동안 식사를 하는 방법은 각 음식을 먹는 데에 드는 시간 T에 대하여 정확히 i-T분동안 음식을 먹는 데에 드는 시간의 합으로 나타낼 수 있음을 알 수 있다.

위의 성질을 점화식으로 나타내 문제를 해결하자.

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

#include <iostream>
using namespace std;
typedef long long ll;

int N, M;
ll dp[1001];
int T[30];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> M >> N;
	for (int n = 0; n < N; n++) cin >> T[n];

	dp[0] = 1;
	for (int i = 1; i <= M; i++) {
		for (int n = 0; n < N; n++) {
			if (i >= T[n]) dp[i] += dp[i - T[n]];
		}
	}

	cout << dp[M];
}