글 읽기 - [질문중]반례를 못찾겠습니다

nablekim94 4년 전 0

채점 결과는 제출하자마자 "틀렸습니다"이고요.

어느 예외 케이스에서 틀린 것인지 못찾고 있습니다...

제가 생각한 방법은...

1) 1번 선수를 4번째 타석에 올 수 있도록 한 '타선 순서'를 순열을 통해 구합니다. >> 재귀함수(dfs)를 이용하여 구함

*** 0번 부터 시작하는 배열의 인덱스를 그대로 사용하려고 선수 번호나 순서를 "0~8" 범위로 사용하였습니다.

2) 정한 타순으로 N이닝 동안 얻을 수 있는 득점을 계산하고

3) 이전까지 구했었던 최대 득점값과 비교하여 갱신합니다.

도움을 주시면 감사하겠습니다!

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

int G[51][9] = { 0, };	// 이닝, 선수별 성적 데이터
int order[9] = { 1, 2, 3, 0, 4, 5, 6, 7, 8 };	// 타순

int N;
int max_score = 0;

void swap(int a, int b) {
	int temp = order[a];
	order[a] = order[b];
	order[b] = temp;
}

// N 이닝동안 얻을 수 있는 점수 계산
int get_score() {
	int score = 0;		// 총점
	int attacker = 0;	// 타석에 들어설 선수

	// N 이닝동안
	for (int i = 0; i < N; i++) {
		int outCount = 0;

		// 1~3루수에 플레이어가 있는가
		bool base[4] = { false, };

		// 각 이닝마다 아웃카운트가 2이하일때 동안
		while (outCount <= 2) {
			// 공격자의 타격
			int hit = G[i][order[attacker]];

			// 안타~홈런
			if (hit != 0) {
				// 이미 나가있는 주자들
				for (int j = 3; j > 0; j--) {
					if (base[j]) {
						// 홈을 지나친 경우 점수 증가
						if (j + hit >= 4)
							score++;
						else
							base[j + hit] = true;

						// 기존의 베이스는 false로 처리
						base[j] = false;
					}
				}

				// 이제 나가는 주자
				if (hit == 4)
					score++;
				else
					base[hit] = true;
			}
			else
				outCount++;

			// 다음 타자 차례
			attacker = (attacker + 1) % 9;
		}
	}
	return score;
}

void get_player0rder(int depth) {
	// k개를 다 뽑았다면 == 타순을 정했다는 뜻
	if (depth == 9) {
		// 정한 타순으로 얻을 수 있는 득점 계산
		int score = get_score();

		// 최대값 비교
		if (max_score < score)
			max_score = score;
		return;
	}

	// 3번째 인덱스(4번째 타석)은 이미 정해져 있으므로 스킵
	if (depth == 3) {
		get_player0rder(depth + 1);
		return;
	}

	for (int i = depth; i < 9; i++) {
		if (i == 3)
			continue;
		swap(depth, i);
		get_player0rder(depth + 1);
	}
}

int main() {
	//freopen("Text.txt", "r", stdin);

	scanf("%d", &N);

	// N이닝 동안의 선수별 성적을 입력받음
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 9; j++)
			scanf(" %d", &G[i][j]);
	}

	// 순열을 통해 타순 정하기
	get_player0rder(0);
	
	printf("%d", max_score);

	return 0;
}

rootsquare 3년 전 0

반례입니다.

입력:

1 2 4 3 0 2 1 0 3

1 2 1 2 0 0 0 0 1

3 4 2 3 1 2 3 4 0

0 1 2 3 4 2 1 0 0

0 0 0 0 0 0 1 4 4

0 4 0 4 0 4 0 4 0

0 4 2 2 2 2 2 2 2

1 1 1 1 1 1 1 1 0

0 2 0 3 0 1 0 2 0

1 2 4 3 0 2 1 0 3

1 2 1 2 0 0 0 0 1

3 4 2 3 1 2 3 4 0

0 1 2 3 4 2 1 0 0

0 0 0 0 0 0 1 4 4

0 4 0 4 0 4 0 4 0

0 4 2 2 2 2 2 2 2

1 1 1 1 1 1 1 1 0

0 2 0 3 0 1 0 2 0

1 2 4 3 0 2 1 0 3

1 2 1 2 0 0 0 0 1

3 4 2 3 1 2 3 4 0

0 1 2 3 4 2 1 0 0

0 0 0 0 0 0 1 4 4

0 4 0 4 0 4 0 4 0

0 4 2 2 2 2 2 2 2

1 1 1 1 1 1 1 1 0

0 2 0 3 0 1 0 2 0

1 2 4 3 0 2 1 0 3

1 2 1 2 0 0 0 0 1

3 4 2 3 1 2 3 4 0

0 1 2 3 4 2 1 0 0

0 0 0 0 0 0 1 4 4

0 4 0 4 0 4 0 4 0

0 4 2 2 2 2 2 2 2

1 1 1 1 1 1 1 1 0

0 2 0 3 0 1 0 2 0

1 2 4 3 0 2 1 0 3

1 2 1 2 0 0 0 0 1

3 4 2 3 1 2 3 4 0

0 1 2 3 4 2 1 0 0

0 0 0 0 0 0 1 4 4

0 4 0 4 0 4 0 4 0

0 4 2 2 2 2 2 2 2

1 1 1 1 1 1 1 1 0

0 2 0 3 0 1 0 2 0

3 4 2 3 1 2 3 4 0

0 1 2 3 4 2 1 0 0

0 0 0 0 0 0 1 4 4

0 4 0 4 0 4 0 4 0

0 4 2 2 2 2 2 2 2

이 코드의 출력: 495

올바른 출력: 500

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

문제

문제

출처

ICPC

[질문중]반례를 못찾겠습니다

nablekim94 4년 전 0

rootsquare 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말