백준 Gold 4 배수 공사

배수 공사 (백준 Gold 4)

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

임의의 파이프 종류 N과 원하는 길이 x가 존재할때
x를 만들 수 있는 경우의 수를 구하는 문제

• 파이프는 길이 l과 수량 c가 주어진다
  

풀이 방법

dp 정의

• dp[i][j] : i번째 파이프까지 사용하여 j길이를 만들 수 있는 경우의 수
  

다음 상태 이동(점화식)

• dp[i][j] += dp[i-1][j - nowL * k]
  
  • k 개수만큼 돌면서 가능한 여부를 현재 값에 넣어줌
    
• dp[0][0] = 1
  (길이 0을 만드는 경우는 아무것도 사용하지 않는 것)
  

순회 방식

• 내림차순 선택
  

• 오름차순도 가능은 해보이나
  이 때는 0 대신 -1 같은 초기화를 해야 할 것으로 보인다
  

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	/*
		dp[i][j] : i번째 파이프까지 사용하여 j 길이를 만들 수 있는 경우의 수

		점화식?
		dp[i][j] = dp[i][j-len[i]] + 1 (단 dp[i][j]를 만들 수 있다면)

		이거 for문 사용해서
		counts[i] 만큼 돌려야 함

		내림차순
	*/

	int n, x;
	cin >> n >> x;

	vector<int> lens(n);
	vector<int> counts(n);

	for (int i = 0; i < n; i++)
	{
		cin >> lens[i];
		cin >> counts[i];
	}

	vector<vector<int>> dp(n + 1, vector<int>(x + 1, 0));
	dp[0][0] = 1;

	for (int i = 1; i <= n; i++)
	{
		int nowL = lens[i - 1];
		int nowC = counts[i - 1];

		for (int j = x; j >= 0; j--)
		{
			for (int k = 0; k <= nowC; k++)
			{
				if (j - nowL * k < 0)
					continue;

				dp[i][j] += dp[i-1][j - nowL * k];
			}
		}
	}

	cout << dp[n][x];

	return 0;
}

결과

배낭 문제에 조금 익숙해진 기분이 든다