월드컵

https://www.acmicpc.net/problem/6987

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	8325	2402	1702	31.379%

문제

월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다.

조별 리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다.

다음은 가능한 결과와 가능하지 않은 결과의 예이다.

네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다.

승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0이다.

출력

입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.

예제 입력 1

5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4
4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3
5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5
5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4

예제 출력 1

1 1 0 0

출처

Olympiad > 한국정보올림피아드 > KOI 2008 > 초등부 2번

Olympiad > 한국정보올림피아드 > KOI 2008 > 중등부 1번

• 빠진 조건을 찾은 사람: djm03178
• 데이터를 추가한 사람: dlwocks31, kyo20111

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

처음 문제에 대한 접근을 입력 받은 예제에서 승/무/패에 대한 데이터를 가지고 해결하는 방법으로 생각하여 조건을 추가하면서 해결하려고 했다.

1시간 정도 해보다…. 내가 못하는 건지 계속 다른 결과만 나왔다.

고민하다가 알고리즘 분류에서 브루트 포스와 백트래킹이 보이길래… 아 하나하나 해서 비교해 보는 것이 좋겠구나 해서 방향을 바꾸었다.

길을 잘못 들어서 고민을 많이 한 문제

가능한 경기는 총 15경기 배열로 어느 팀과의 경기인지 표시

문제를 입력받는 부분도 처음에는 string 값으로 받아서 처리하려고 하다가

테스트 케이스는 4가지로 이미 정해져 있고 / 팀은 6팀 / 결과는 승 무 패 -> 4 / 6 / 3 배열로 처리하였다.

테스트 케이스와 비교하는 부분은 DFS로 비교하였다.

game의 수가 15번이면 테스트 케이스와 비교하여 스코어가 다른값 없이 통과하면 결과에 1을 넣어주어 나중에 출력 (기본 0)

통과된 코드

#include <iostream>

using namespace std;

// 문제의 예상 결과를 넣기
int predictedArr[4][6][3];

// 가능한 경기는 총 15경기
int gameArr1[15] = {0,0,0,0,0,1,1,1,1,2,2,2,3,3,4};
int gameArr2[15] = {1,2,3,4,5,2,3,4,5,3,4,5,4,5,5};

// Win Draw Lose 결과
int scoreWDL[6][3];

// 결과를 저장해서 마지막에 출력
int result[4];


void Initalization()
{
	//결과 초기화
	for (int i = 0; i < 4; i++)
	{
		result[i] = 0;
	}

	// 예상 스코어를 받습니다.
	for (int n = 0; n < 4; n++)
	{
		for (int i = 0; i < 6; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				cin >> predictedArr[n][i][j];
			}
		}
	}
}

void CheckScoreRecursive(int gameCnt)
{
	// 만약 모든 경기가 끝났다면
	if (gameCnt == 15) {
		//비교
		for (int n = 0; n < 4; n++) {

			bool check = true;

			for (int i = 0; i < 6; i++) {
				for (int j = 0; j < 3; j++) {
					if (predictedArr[n][i][j] != scoreWDL[i][j]) {
						check = false;
						break;
					}
				}

				// 예측 결과가 가능하면 브레이크
				if (!check) break;
			}

			// 해당 결과가 가능하면 진입
			if (check) {
				result[n] = 1;
			}
		}

		return;
	}

	// 기준은 Arr1
	// 승리했을 경우
	scoreWDL[gameArr1[gameCnt]][0]++;
	scoreWDL[gameArr2[gameCnt]][2]++;
	CheckScoreRecursive(gameCnt + 1);
	scoreWDL[gameArr1[gameCnt]][0]--;
	scoreWDL[gameArr2[gameCnt]][2]--;

	// 무승부일 경우
	scoreWDL[gameArr1[gameCnt]][1]++;
	scoreWDL[gameArr2[gameCnt]][1]++;
	CheckScoreRecursive(gameCnt + 1);
	scoreWDL[gameArr1[gameCnt]][1]--;
	scoreWDL[gameArr2[gameCnt]][1]--;

	// 패배의 경우
	scoreWDL[gameArr1[gameCnt]][2]++;
	scoreWDL[gameArr2[gameCnt]][0]++;
	CheckScoreRecursive(gameCnt + 1);
	scoreWDL[gameArr1[gameCnt]][2]--;
	scoreWDL[gameArr2[gameCnt]][0]--;
}

int main()
{
	Initalization();

	// DFS로 시작 
	CheckScoreRecursive(0);

	// 결과 출력
	for (int i = 0; i < 4; i++)
	{
		cout << result[i] << " ";
	}

	return 0;
}