글 읽기 - 안녕하세요 이 코드의 반례 부탁드립니다.

pminsu2 4년 전 0

해당 테스트 케이스는 모두 맞는데.. 그리고 로직도 다시 살펴보고 있는데요.

질문에 올라온 테스트 케이스 모두 해도 맞는데.. 혹시 반례를 알 수 있을까요

부탁 드립니다 ㅠ

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

using namespace std;

/*

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다.
(r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

*/
struct JossValue {

	int direction; // 1: up, 2: under, 3: right, 4: left
	int size;
	int speed;

};

//JossValue map[100][100] = { {0,0,0}, };
int x;
int y;
int Num;
vector<JossValue> tempMap[101][101];
vector<JossValue> Map[101][101];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
void moveJoss() {

	// 1: up , 2: under, : x값 변함
	// 3: right, 4: left : y값 변함
	// 왼쪽과 위의 경계선은 1
	// 오른쪽 경계선은 y, 아랫쪽 경계선은 x
	// 겹칠 경우에는 크기가 큰 상어가 작은 상어를 모두 잡아먹는다.
	// 행으로 움직였을 때 1로 가면 방향이 
	// 2*(y-1), 2*(x-1) 일 때 원래 순서대로 돌아온다.

	int yStay = 2 * (y - 1);
	int xStay = 2 * (x - 1);

	for (int i = 1; i <= x; i++) {
		for (int j = 1; j <= y; j++) {

			tempMap[i][j] = Map[i][j];
			Map[i][j].clear();

		}
	}
	for (int i = 1; i <= x; i++) {
		for (int j = 1; j <= y; j++) {

			if (tempMap[i][j].size() == 0) continue;


			int nx = i;
			int ny = j;
			int tempDir = tempMap[i][j].front().direction;
			int tempSpeed = tempMap[i][j].front().speed;
			int tempSize = tempMap[i][j].front().size;


			// 1: up , 2: under, : x값 변함
			// 3: right, 4: left : y값 변함

			if (tempDir == 1 || tempDir == 2) {

				if (tempSpeed > xStay) {
					tempSpeed = tempSpeed % xStay;
				}


				for (int a = 0; a < tempSpeed; a++) {

					nx = nx + dx[tempDir - 1];
					ny = ny + dy[tempDir - 1];


					if (nx < 1) {
						tempDir = 2;
						nx = 2;
					}

					if (nx > x) {

						tempDir = 1;
						nx = x - 1;
					}


				}

			}

			else{
				if (tempSpeed > yStay) {
					tempSpeed = tempSpeed % yStay;
				}


				for (int j = 0; j < tempSpeed; j++) {

					nx = nx + dx[tempDir - 1];
					ny = ny + dy[tempDir - 1];

					if (ny < 1) {
						tempDir = 3;
						ny = 2;
					}

					if (ny > y) {
						tempDir = 4;
						ny = y - 1;
					}

				}


			}

			JossValue jossvalue;
			jossvalue.speed = tempSpeed;
			jossvalue.direction = tempDir;
			jossvalue.size = tempSize;
			Map[nx][ny].push_back(jossvalue);
			//cout << "움직 인 후 조스 : " << nx << " , " << ny << endl;


		}
	}
}

void surviceJoss() {

	for (int i = 1; i <= x; i++) {

		for (int j = 1; j <= y; j++) {

			if (Map[i][j].size() > 1) {
				//사이즈 큰 값을 갖기 위한 vc
				vector<int> tempIndex;
				for (int a = 0; a < Map[i][j].size(); a++) {
					int temp = Map[i][j].at(a).size;
					tempIndex.push_back(temp);
				}
				int index = max_element(tempIndex.begin(), tempIndex.end()) - tempIndex.begin();

				JossValue jossvalue;
				jossvalue.direction = Map[i][j].at(index).direction;
				jossvalue.size = Map[i][j].at(index).size;
				jossvalue.speed = Map[i][j].at(index).size;

				Map[i][j].clear();
				Map[i][j].push_back(jossvalue);

			}
		}
	}
}
int catchJoss() {

	int result = 0;
	int startPoint = 1;

	while (startPoint <= y) {

		for (int i = 1; i <= x; i++) {

			if (Map[i][startPoint].size() == 0) {
				continue;
			}
			else {
				cout << Map[i][startPoint].front().size << endl;
				result += Map[i][startPoint].front().size;
				Map[i][startPoint].clear();
				break;
			}
		}
		moveJoss();
		surviceJoss();
		startPoint++;

	}


	return result;




}

int main() {

	cin >> x >> y >> Num;
	if (Num == 0) {
		cout << -1 << endl;
		return 0;
	}
	for (int i = 0; i < Num; i++) {

		int tempX;
		int tempY;
		int tempSpeed;
		int tempDirection;
		int tempSize;

		cin >> tempX >> tempY >> tempSpeed >> tempDirection >> tempSize;
		JossValue jossvalue;
		jossvalue.direction = tempDirection;
		jossvalue.size = tempSize;
		jossvalue.speed = tempSpeed;

		Map[tempX][tempY].push_back(jossvalue);
	}
	int answer = catchJoss();
	cout << answer << endl;
}

dodi258 4년 전 1

반례로 알려주신거에서

4번 째 줄에 (3, 444) 가 있는데요..

1번 째 줄에 배열 정의는 50 by 50 으로 해놓으셔서

out of Bounds Exception 이되네요

herdson 4년 전 7

다시 수정된 테스트 케이스를 가져왔습니다.

50 19
9 21 1 999
50 4 4 500
49 222 3 200
48 12 2 45
47 36 1 900
3 20 3 444
8 4 2 49
3 40 4 50
2 460 2 4444
23 500 3 12
1 200 1 123
44 123 3 125
40 222 3 17
44 333 3 57
40 1 1 4
10 50 2 406
36 177 4 50
46 120 4 7
50 28 4 54

output : 8218
answer : 7718

pminsu2 4년 전 2

herdson님 반례 감사드립니다. dodi258님 감사합니다.

1. 해당 문제는 155번 줄에 jossvalue.speed 항목에 size를 대입하여 오답이 발생하였습니다.

2. 추가적으로 201번줄에 조스가 없는 경우 0을 출력해야하는데 -1을 출력하는 문제 또한 있었습니다.

문제 푸시는 분께 도움이 되었으면 좋겠습니다.

robin00q 4년 전 1

herdson님 반례에 오류가 있는 것 같습니다.

제 코드의 경우 정답이 7668로 나오는데 일단 통과는 하였습니다. 제가 문제가 아니라면 herdson님의 반례가 틀린 것일수도 있네요

paraworld 3년 전 0

죄송합니다만 위 반례에 크기가 같은 상어가 2마리 있어서 작동하지 않습니다. (크기 50짜리가 2마리 있네요)

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

문제

문제

출처

ICPC

안녕하세요 이 코드의 반례 부탁드립니다.

pminsu2 4년 전 0

dodi258 4년 전 1

herdson 4년 전 7

pminsu2 4년 전 2

robin00q 4년 전 1

paraworld 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말