[PS] 지금 자면 꿈을 꾸지만 / C++ (백준 32029번)

 

2024 UCPC 예선 E번으로, 대회 당시에 내가 풀었던 문제다. 간단한 그리디 문제지만 접근을 잘못해서 시간을 많이 소비했었다. 대회가 끝나고 다시 풀어보니 너무 간단해서 앞으로 난이도를 알 수 없는 문제에 너무 쫄지 말자는 교훈을 줬던 문제이다.

 

해결 방법

$A$를 기준으로 정렬하고, n개의 문제에 대해 브루트 포스 형식으로 먼저 끝낼 과제를 정한 뒤, 단축된 시간으로 풀 수 있는 문제의 수들을 구하면 되는 간단한 로직이다. n값이 아주 작기 때문에 $O(n^3)$도 가능하다.

#include<iostream>
#include<algorithm>
using namespace std;
int t[101], vi[101];

int main()
{
	int n, a, b, answer=0, c, solve;
	scanf("%d %d %d", &n, &a, &b);
	for (int i = 1; i <= n; i++)scanf("%d", &t[i]);
	sort(t + 1, t + n + 1);
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= 100; j++)vi[j] = 0;
		if (i != 0) {
			c = 0; solve = 0;
			for (int j = 1; j <= n; j++) {
				if (solve == i)break;
				if (t[j] >= c + a) {
					solve++;
					c += a;
					vi[j] = 1;
				}
			}
			if (solve != i)break;
		}
		else {
			c = 0;
			solve = 0;
		}
		for (int x = 0; x < a; x++){
			int cc = b * x + c, after_solve = 0, nA = a - x;
			for (int j = 1; j <= n; j++) {
				if (cc + nA <= t[j] && vi[j] == 0) {
					after_solve++;
					cc += nA;
				}
			}

			if (solve + after_solve > answer)answer = solve + after_solve;
		}
	}
	printf("%d\n", answer);
	return 0;
}