글 읽기 - 2905번 반례를 못찾겠습니다

mirine5314 4년 전 0

아무리 반례를 찾아보려고 해도 제 실력선에서는 반례를 찾을 수가 없었습니다.....

몇 시간 동안 직접 입력해보고, 입력을 랜덤으로 줘서 돌려보기도 했지만 풀지 못했습니다.

코드에 어디가 잘못된걸까요ㅠㅠ

실력이 부족해서 코드가 살짝 더러울 수 있습니다...

#include <iostream>
#include <queue>

int const max = 1000000 + 1;

//색칠되지 않은 부분을 저장할 배열
int pAry[max];

//큐에서 X만큼의 수를 가져와 최소값을 반환하는 함수
int findMin(std::queue<std::pair<int, int> > q, int x) {
	int min = 100;
	for (int i = 0; i < x; i++) {
		if (q.front().first <= min) {
			min = q.front().first;
		}
		q.pop();
	}

	return min;
}

//겹치는 부분을 제외하고 색칠이 되지 않은 부분을 구하는 함수
void paintBrush(std::queue<std::pair<int, int> > q, int x, int pAry[]) {
	int min = 0;
	std::queue<std::pair<int, int> > hq;

	while (1) {
		if (q.size() < x) break;
		
		for (int i = 0; i < x; i++) {
			hq.push(q.front());
			q.pop();
		}
		
		min = findMin(hq, x);
		
		for (int i = 0; i < x; i++) {
			pAry[hq.front().second] = (hq.front().first - min);
			if (!hq.empty()) hq.pop();
		}
	}
}

//겹치는 부분을 구하는 함수
void overlap(std::queue<std::pair<int, int> > q, int n, int x, int pAry[]) {
	int min = 0;

	for (int i = 0; i < n - x; i++) {
		q.pop();
	}

	min = findMin(q, x);
	
	for(int i = 0; i < x; i++){
        //겹치는 곳에 있던 수가 0이거나 새로 저장될 변수보다 작으면 그대로 유지한다. 
		if (pAry[q.front().second] == 0 ||
			pAry[q.front().second] <= (q.front().first - min)) q.pop();
        else {
			pAry[q.front().second] = (q.front().first - min);
			if (!q.empty()) q.pop();
		}
	}
}

//페인트칠하는 횟수를 구하는 함수
int calculationCount(std::queue<std::pair<int, int> > q, int x) {
	int cnt = 0;
	
	while (1) {
		if (q.empty()) break;

		for (int i = 0; i < x; i++) {
			if(!q.empty()) q.pop();
		}
		cnt++;
	}

	return cnt;
}

int main(){
	int n, x;
	int cnt = 0, sum = 0;
	std::fill_n(pAry, max, 100000);
	std::queue<std::pair<int, int> > q;

	std::cin >> n >> x;

	for (int i = 0; i < n; i++) {
		int height;
		std::cin >> height;
		q.push(std::make_pair(height, i));
	}

	paintBrush(q, x, pAry);
    //n과 x가 같으면 겹치는 부분이 없으므로 계산X
	if(n != x) overlap(q, n, x, pAry);
	
	cnt = calculationCount(q, x);
	
	for (int i = 0; i < n; i++) {
		sum += pAry[i];
	}
	
	std::cout << sum << std::endl;
	std::cout << cnt << std::endl;

    return 0;
}

sait2000 4년 전 0

반례입니다.

in:
4 2
1 2 3 3

out:
0
3

mirine5314 4년 전 0

감사합니다. 덕분에 출력은 맞게 나오는 것 같습니다.

근데 시간초과 때문에 해결을 못하겠네요 ㅠㅠ

답변 감사드립니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2905번 반례를 못찾겠습니다

mirine5314 4년 전 0

sait2000 4년 전 0

mirine5314 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말