[백준] 17213번 : 과일 서리

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 과일의 종류가 N가지이고 훔쳐야 하는 과일의 개수가 M개일 때, 과일 종류가 1~n개일 때 각각 훔쳐야 하는 과일 개수가 1~m개일 때 가능한 경우의 수를 2차원 배열인 dp에 갱신하는 Bottom-Up 방식으로 풀었다.

1) 과일의 종류 n과 훔쳐야 하는 과일 개수 m을 입력 받아 저장한다.

2) 2차원의 dp 배열의 1번째 행은 전부 1로 초기화한다. (과일 종류가 1가지인 경우에는 모든 과일을 같은 과일로 훔쳐야 하기 때문에 경우의 수가 1개 밖에 없기 때문이다.)

3) dp 배열을 과일 종류가 i(1~n)일 때 훔쳐야 하는 과일 개수가 j(1 ~ m)인 경우 각각에 대해 갱신한다.

• dp[i][j]는 i개의 과일 종류가 있고, 훔쳐야 하는 과일 개수가 j일 때의 가능한 경우의 수
  • dp[3][5]를 구하는 과정을 예시로 들면
  • 일단 첫 번째 과일을 하나 훔쳤다고 가정하면, dp[i][j]는 첫 번째 과일을 하나만 훔칠 경우 + 첫 번째 과일을 하나 초과해 훔칠 경우의 수가 된다.
  • 첫 번째 과일을 하나만 훔친다면 이 때의 경우의 수는 나머지 두 과일로 j - 1개의 과일을 훔치는 경우의 수 (== dp[2][j - 1])
  • 첫 번째 과일을 하나 초과해 훔친다면 이 때 경우의 수는 세 과일로 j - 1개의 과일을 훔치는 경우의 수 (== dp[3][j - 1])
  • 이를 점화식으로 표현하면
    • dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]

4) dp[n][m]를 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <algorithm>

using namespace std;
int dp[11][31];

int solution(int n, int m)
{
	for (int i = 1; i <= m; i++)
		dp[1][i] = 1;

	for (int i = 2; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
	}

	return dp[n][m];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int n, m;
	cin >> n >> m;

	cout << solution(n, m);
}