백준 24508 나도리팡 (c++) : 피너클

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

24508번: 나도리팡

 

그리드와 투 포인터를 이용한 구현문제다.

 

cin >> n >> k >> t;
v.resize(n);
for (int i = 0; i < n; i++) cin >> v[i];

sort(v.begin(), v.end());

바구니안 나도리의 수를 입력받은 다음 정렬해준다.

앞에있는 적은 나도리들로 뒤에있는 많은 나도리들의 수를 채워 k개를 만들어줄것이다.

int start = 0, end = n - 1, d = 0;
while (v[start] == 0) start++, d++;

start와 end는 투 포인터에 사용될 변수고 d는 나도리의 수가 0이된 바구니의 수다.

입력값에 0도 있기때문에 미리 0인 바구니를 처리해준다.

while (start <= end) {
	if (start == end) {
		if (v[start] >= k) d++;
		break;
	}

start가 end보다 작거나 같은동안 반복한다.

만약 start와 end가 같다면, 즉 바구니가 하나만 남았다면

하나 남은 바구이에 k보다 많거나 같은 양의 나도리가 있다면 전부 터져 0이 될테니 d에 1을 더해준다.

그후 반복문에서 나간다.

int need = k - v[end];
if (t < need) break;

int need는 v[end]가 k개가 되기 위해 필요한 나도리의 수다.

만약 t가 need보다 작다면, 즉 need개를 옮길 시간이 부족하다면 바로 반복문에서 나가준다.

전부 터트릴 시간이 부족하니 더이상 확인할 필요가 없다.

if (v[start] == need) {
	t -= need;
	end--;
	start++;
	d += 2;
}

만약 v[start]와 need같다면 

need개를 옮길것이니 t에서 need를 빼주고

v[end]는 need개가 더해져 k개가 됬으니 전부 터져 0이 된다. end-- 해준다.

그후 v[start]도 v[end]에 전부 전해졌으니 start++ 해준다.

그후 2개의 바구니가 비워졌으니 d에 2를 더해준다.

else if (v[start] > need) {
	v[start] -= need;
	t -= need;
	end--;
	d++;
}

만약 v[start]가 need보다 크다면

v[start]에서 need를 뺴고

t에서 need를 뺴준다.

v[end]가 k개가 됬으니 end-- 해주고

그후 1개의 바구니가 비워졌으니 d에 1을 더해준다.

else if (v[start] < need) {
	v[end] += v[start];
	t -= v[start];
    start++;
	d++;
}
if (t <= 0) break;

만약 v[start]가 need보다 작다면

v[end]에 v[start]를 더해주고

 

 

t에서 v[start]를 빼준다.

v[start]가 0개가 되었으니 start++ 해주고

그후 1개의 바구니가 비워졌으니 d에 1을 더해준다.

 

모든 조건을 확인한후 시간이 남지 않았다면 반복문에서 나간다.

if (d >= n) cout << "YES" << endl;
else cout << "NO" << endl;

만약 0개인 바구니가 n과 같거나 많다면 YES를 출력하고

아니면 NO를 출력한다.

 

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

using namespace std;

int n, k, t;
vector<int> v;

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

	cin >> n >> k >> t;
	v.resize(n);
	for (int i = 0; i < n; i++) cin >> v[i];

	sort(v.begin(), v.end());

	int start = 0, end = n - 1, d = 0;
	while (v[start] == 0) start++, d++;
	while (start <= end) {
		if (start == end) {
			if (v[start] >= k) d++;
			break;
		}

		int need = k - v[end];
		if (t < need) break;

		if (v[start] == need) {
			t -= need;
			end--;
			start++;
			d += 2;
		}
		else if (v[start] > need) {
			v[start] -= need;
			t -= need;
			end--;
			d++;
		}
		else if (v[start] < need) {
			v[end] += v[start];
			t -= v[start];
			start++;
			d++;
		}
		if (t <= 0) break;
	}
	if (d >= n) cout << "YES" << endl;
	else cout << "NO" << endl;
}

전체코드다.