[C/C++] Codeforce 189A - Cut Ribbon (DP, Brute Force)

A. Cut Ribbon

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:

After the cutting each ribbon piece should have length a, b or c.

After the cutting the number of ribbon pieces should be maximum.

Help Polycarpus and find the number of ribbon pieces after the required cutting.

 

Input

The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.

 

Output

Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.

 

문제는 쉽게 생각해서 a, b, c 길이를 가진 끈들로(개수는 상관없음) 길이 n의 끈을 만들 때 a + b + c의 최댓값을 구하라는 문제이다. 즉, 정확히 길이 n을 맞춘다는 가정하에 a, b, c끈을 섞어서 사용해도 되고 하나의 끈만 사용해도 된다는 의미이다. 

위의 예시에서 5 5 3 2 입력의 경우 제일 짧은 끈인 c끈을 사용하면 끈 개수의 합이 최대가 되지만 길이가 2인 끈만으로는 길이 5를 맞출 수 없기 때문에 b끈 1개, c끈 1개씩 해서 2 + 3 = 5 이므로 답은 2가 되는 것이다.

<DP 풀이법>

#include<stdio.h>
#include<algorithm>

int DP[5000]; 

int main(void)
{
	int n, a, b, c;
	int i;
	int ans;
	scanf("%d %d %d %d", &n, &a, &b, &c);
	DP[0] = 0;

	for (int i = 1; i <= n; i++)
	{
		DP[i] = -1;

		if (i >= a)
			if (DP[i - a] >= 0) 
				if (DP[i - a] >= DP[i])
					DP[i] = DP[i - a] + 1;

		if (i >= b) 
			if (DP[i - b] >= 0) 
				if (DP[i - b] >= DP[i]) 
					DP[i] = DP[i - b] + 1;
		
		if (i >= c)
			if (DP[i - c] >= 0)
				if (DP[i - c] >= DP[i])
					DP[i] = DP[i - c] + 1;
	}
	ans = DP[n];
	printf("%d", ans);

}

다이나믹 프로그래밍(dp)을 구현하는데 익숙하지 않아서 교수님의 풀이를 참고하였는데 아직도 잘 이해가 가지 않는다...

 

<Brute Force 풀이법>

#include<stdio.h>
#include<algorithm>

using namespace std;


int main(void)
{
	int n, a, b, c;
	int max = -1;
	scanf("%d %d %d %d", &n, &a, &b, &c);

	for (int i = 0; i <= n / a; i++)
	{
		for (int j = 0; j <= (n - (a * i)) / b; j++) // 전체길이n에서 a*i만큼 뺀 길이에서 가능한 j의 경우들
		{
			if ((n - (a * i + b * j)) % c == 0) // 남은 끈길이가 c로 나눠질 때
			{
				int k = (n - (a * i + b * j)) / c; // i,j값이 결정되었으므로 k값도 결정된다.
				if (max < i + j + k) max = i + j + k; // 최대값 구하기
			}
		}
	}

	printf("%d", max);
}

브루트 포스 법은 dp보다 상대적으로 구현이 쉬웠다. for문 i, j, k를 사용해서 모든 부분을 탐색할 수 있지만 시간 복잡도를 줄이기 위해 i, j가 결정되면 k는 "k = (n - (a * i + b * j)) / c"로 구하였고 각 끈들의 개수의 최댓값을 구하였다. 대신 알고리즘 특성상 탐색해야 하는 경우의 수가 많아지면 시간이 오래 걸릴 것이다.

 

 

https://codeforces.com/contest/189/problem/A

Problem - A - Codeforces