글 읽기 - 알고리즘 검토 부탁드립니다.

iamthejiheee 4년 전 0

스티커 배열을 입력받고, 우선순위 큐에 넣어서 큰 값을 가장 우선순위로, 값이 같다면 x좌표가 작은 쪽으로 넣었습니다.

테스트 케이스나 반례도 다 맞는데, 어떤 식으로 고쳐야하는지 아니면 아예 새로 로직을 구성해야하는지 조언해주시면 감사하겠습니다.

#include <bits/stdc++.h>

using namespace std;

struct Data {
	int x, y, value;
	Data(int a, int b, int c) {
		x = a;
		y = b;
		value = c;
	}

	bool operator < (const Data &b) const {
		if (value == b.value) {
			return x < b.x;
		}
		else return value < b.value;
	}
};

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int main() {
	ios_base::sync_with_stdio(false);
	int T, n;
	cin >> T;


	int res = 0;
	for (int i = 0; i < T; i++) {
		cin >> n;
		res = 0;
		vector< vector<int> > sticker(2, vector<int>(n, 0));
		priority_queue<Data> Q;
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < n; j++) {
				cin >> sticker[i][j];
				Q.push(Data(j, i, sticker[i][j]));
			}
		}

		while (!Q.empty()) {
			int x = Q.top().x;
			int y = Q.top().y;
			if (sticker[y][x] == -1) Q.pop();
			else {
				cout << y << ", " << x << " : " << Q.top().value << endl;
				res += Q.top().value;
				Q.pop();

				for (int j = 0; j < 4; j++) {
					int xx = x + dx[j];
					int yy = y + dy[j];
					if (xx >= 0 && xx < n && yy >= 0 && yy < 2) {
						sticker[yy][xx] = -1;
					}
				}
			}
		}
		cout << res << endl;
	}


	return 0;
}

skysign 3년 전 0

프라이어티 큐를 사용해서 큰값을 찾기 보다는,

특정 컬럼을 사용하지 않고, 넘어가는 것을 고려해 보시는건 어떨까요?

문제풀이는 아래영상 참고하세요. 파이팅입니다.~

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

문제

문제

출처

ICPC

알고리즘 검토 부탁드립니다.

iamthejiheee 4년 전 0

skysign 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말