[BOJ 6987] 월드컵 (Java)

BOJ 6987 월드컵

문제풀이

재미있는 문제였다. 처음 생각한 것은 전체 경기의 모든 경우를 입력으로 주어지는 것 처럼 스트링으로 만들어서 Set에 저장하고 입력이 들어올때 해당 경우가 Set에 존재하는지 확인하는 방식이였다. 하지만 메모리 초과!

이 문제는 시간 제한 1초에 메모리 128MB로 좀 빡빡하다. 그래서 다른 방법을 생각해내야 했다. 가지치기를 획기적으로 하기위해서 반대로 생각해보기로 했다. 만들어놓은 모든 경우와 대조하는 것이 아니라 입력으로 주어진 데이터를 바탕으로 15경기가 진행 가능한지 확인하는 방식을 생각했다. 하지만 또 틀렸다!

왜일까... 계속 생각하다가 깨달은 것은 바로 각 팀마다 5경기씩 진행하고 한 경기당 승/무/패 중 하나를 가지게되므로 6팀 * 5경기 = 승/무/패의 총합이 30이하여야 한다는 것이다. 이 조건을 걸고 다시 제출했더니 통과!

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int[] home = {0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4};
	static int[] away = {1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5};
	static int[][] score;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		score = new int[6][3];
		
		for(int i = 0 ; i < 4 ; ++i) {
			int total = 0;
			st = new StringTokenizer(br.readLine());
			
			for(int r = 0 ; r < 6 ; ++r) {
				for(int c = 0 ; c < 3 ; ++c) {
					score[r][c] = Integer.parseInt(st.nextToken());
					total += score[r][c];
				}
			}
			
			if(total > 30) {
				System.out.print(0 + " ");
				continue;
			}
			
			if(play(0)) System.out.print(1 + " ");
			else System.out.print(0 + " ");
		}
	}

	private static boolean play(int game) {

		if(game == 15) {
			return true;
		}

		// 홈 팀이 이기는 경우
		if(score[home[game]][0] > 0 && score[away[game]][2] > 0) {
			score[home[game]][0]--;
			score[away[game]][2]--;
			if(play(game + 1)) return true;
			score[home[game]][0]++;
			score[away[game]][2]++;
		}
		
		// 어웨이 팀이 이기는 경우 
		if(score[home[game]][2] > 0 && score[away[game]][0] > 0) {
			score[home[game]][2]--;
			score[away[game]][0]--;
			if(play(game + 1)) return true;
			score[home[game]][2]++;
			score[away[game]][0]++;
		}
		
		// 비기는 경우 
		if(score[home[game]][1] > 0 && score[away[game]][1] > 0) {
			score[home[game]][1]--;
			score[away[game]][1]--;
			if(play(game + 1)) return true;
			score[home[game]][1]++;
			score[away[game]][1]++;
		}
		
		return false;
	}
}