codeforces _ 189A _ A. Cut Ribbon

2020-05-06 · 배운 것 · 3분 읽기

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

Problem - 189A - Codeforces

풀이방법

시간은 1초, n,a,b,c는 최대 4000이다.
조건은
1. piece는 무조건 a or b or c
2. 최대로 자를수 있는 값을 구하라

완전탐색으로 할시 최악의 경우 ( a,b,c가 1, n이 4000일때 ) 4000! * 3일수 있다. 그러므로 완전탐색은 탈락이고 시간을 줄일수 있는 dp를 써보자.

dp[value] : value일때 최대로 자를수 있는 개수
그리고 a, b, c를 하나씩 순서대로 밑의 조건대로 넣어보자.

1. value % piece (a or b or c) == 0 일때
dp[value] = max(dp[value], value / piece[i]);

2. 그외
2. 1. dp[value] >0 && (value + piece <=n)
dp[value + piece[i]] = max(dp[value + piece[i]], dp[value] + 1);

전체코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[4001];
int n;
vector<int> piece;

void Input()
{
	int a, b, c;
	cin >> n >> a >> b >> c;
	piece = vector<int>{ a, b, c };
	sort(begin(piece), end(piece));
}

void solve()
{
	for (int value = 0; value <= n; value++)
	{
		for (int i = 0; i < 3; i++)
		{
			if (value % piece[i] == 0)
				dp[value] = max(dp[value], value / piece[i]);
			else
			{
				if (dp[value] > 0)
					if (value + piece[i] <= n)
						dp[value + piece[i]] = max(dp[value + piece[i]], dp[value] + 1);
			}
		}
	}
	cout << dp[n] << '\n';
}

int main()
{
	Input();
	solve();
	return 0;
}

후기

쉬운 문제였다. 하지만 나는 뭔가 규칙이 있을줄 알고 규칙찾다가 시간을 조금썼다. 그냥 dp문제였는데..