글 읽기 - 테스트 케이스에서 점수 카운팅할때

jerryprk 4년 전 0

0 4 4 4 4 4 4 4 4 같은경우나

예제 1번 2번같은경우는 문제없이 잘 돌아간다고 생각합니다

근데

숫자가 섞여있는경우

3번타자를 고정시키고 모든순열을 찾았을때,

해당 라운드의최대값이 설정되는것을 출력해보았는데

이론상 맞지만, 정답과는 달랐습니다

예제 4번과 예제 6번의경우

최대치가 나올수있는 최적의 순열이 무엇이있는건가요?
소스에서는 왜 그값이아닌 over된 순열이 나오는걸까요

출력해서 확인할 부분은 주석처리되어잇슴니다

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;

#define MAX 9
int playround, highcost, result;
int pixplayer, nextplayer;
int player[MAX];
bool visit[MAX];
void play(int ening[], int nowplayer) {
	int totalcost = 0;
	int outcount = 0;
	bool ground[4] = { 0, };
	while (1) {
		if (outcount == 3) {
			break;
		}
        // 해당 타자의 진루 0 4 제외 default
		switch (ening[nowplayer]) {
		case 0: 
			outcount++;
			break;
		case 4:
			for (int i = 1; i < 4; i++) {
				if (ground[i]) totalcost++;
			}
			memset(ground, false , sizeof ground);
			totalcost++;
			break;
		default :
			for (int i = 3; i > 0; i--) {
				if (ground[i]) {
					if (i + ening[nowplayer] > 3) {
						totalcost++;
						ground[i] = false;
					}
					else {
						ground[i] = false;
						ground[i + ening[nowplayer]] = true;
					}
				}
			}
			ground[ening[nowplayer]] = true;
			break;
		}
        // 0~8까지이므로 9일경우 0으로
		nowplayer = nowplayer + 1 > MAX - 1 ? 0 : nowplayer + 1;
		/*
		cout << "ground : ";
		for (int i = 0; i < 4; i++)
			printf("%d ", ground[i]);
		cout << "\t totalcost : " << totalcost << endl;
		*/
	}
    // 최대치가 나올수있는경우에, 증가된 다음 플레이어의 번호를 저장해주고
    // 최대치 갱신
	if (highcost < totalcost) {
		highcost = totalcost;
		nextplayer = nowplayer;
        /*
		cout << endl << "player : ";
		for (int i = 0; i < MAX; i++)
			printf("%d ", ening[i]);
		cout << endl;
        */
		//printf("highcost : %d\n", highcost);
		//printf("pixplayer :%d\tnextplayer :%d\n", pixplayer, nextplayer);
	}
}
void setplay(int playlist[]) {
    // permutation된 타자 순번의 값을 대입
	int nowening[MAX] = { 0, };
	for (int i = 0; i < MAX; i++) {
		nowening[i] = player[playlist[i]];
	}
	/*
	cout << "playlist : ";
	for (int i = 0; i < MAX; i++)
		printf("%d ", playlist[i]);
	
	
	cout << endl << "player : ";
	for (int i = 0; i < MAX; i++)
		printf("%d ", nowening[i]);
	cout << endl;


	printf("startplayer : %d\n", nextplayer);
	
	*/
    // 해당 라운드의 시작타자부터 갱신된 타자순번의 진루경우 play시작
	play(nowening, pixplayer);

}
void setplaylist(int index, int cnt, int playlist[]) {
	if (cnt == 3) {
		setplaylist(index, cnt + 1, playlist);
		return;
	}
	playlist[cnt] = index;
	if (cnt == MAX-1) {
		setplay(playlist);
		return;
	}
	for (int i = 1; i < MAX; i++) {
		if (!visit[i]) {
			visit[i] = true;
			setplaylist(i, cnt + 1, playlist);
			visit[i] = false;
		}
	}
}
void permutation() {
	int playlist[MAX] = { 0, };
	for (int i = 1; i < MAX; i++) {
		visit[i] = true;
		setplaylist(i, 0, playlist);
		visit[i] = false;
	}
}
int main() {
#ifdef _CONSOLE
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d", &playround);
	while (playround-- > 0) {
		//cout << endl << "Round : " << playround << endl;
		//printf("startplayer : %d\n", pixplayer);
		highcost = 0;
		for (int i = 0; i < MAX; i++) {
			scanf("%d", &player[i]);
		}

		permutation();
		result += highcost;
		//printf("\nhighcost : %d\ntotalcost : %d\n", highcost, result);
		pixplayer = nextplayer;
	}
	printf("%d", result);
}

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

문제

문제

출처

ICPC

테스트 케이스에서 점수 카운팅할때

jerryprk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말