BOJ 6987 월드컵
끝내주게 풀어봤다.
🔍 문제 접근
1. 그리디한 접근
6개의 국가 간의 승무패 결과가 0~6의 정수로 주어진다.
총 결과를 분석해서 가능한 결과면 1을, 불가능하다면 0을 출력하면 된다.
얼핏 보면 수식으로 그리디하게 접근할 수 있을 것만 같다. 하지만 불가능하다.
- 총 합이 30이여야 한다.
- 승의 합과 패의 합이 같아야한다.
- 무승부의 숫자는 짝수여야하며, 무승부한 국가도 짝수개여야 한다.
- 전승팀은 2개 일 수 없다.
- 전승팀이 1개이더라도 전무 팀이 있으면 안된다.
...
이런 식으로 조건이 계속 추가된다. 무승부 때문이다.
무승부는 특정 팀과 해야하는 싸이클이 생기는 경우가 생기기 때문에,
2팀 간 무승부하고, 나머지가 승무패가 가능한지
3팀 간 무승부하고, 나머지가 승무패가 가능한지
이런식으로 모든 경우를 따져야하고, 결국은 완전탐색을 해야한다는 결론에 이를 수 있다.
그렇다면 완전탐색은 어떤 식으로 해야할까?
2. 완전탐색
두 가지 정도 방법이 있을 것 같다.
A팀이 1승한 경우 -> B팀과 매치한 경우 / C팀과 매치한 경우 ...
A팀이 1승 후 2승한 경우 -> C팀과 매치한 경우 / D팀과 매치한 경우 ...
너무 난잡한 방식이다.
관점을 바꿔서 승무패보다는 매치한 팀들에 주목해보자.
A-B 경기, A-C 경기, A-D 경기 ... D-F 경기, E-F 경기
이런 방식으로 6C2 = 15 로 총 15 종류의 매치업이 나오게 된다.
따라서 이 각각의 매치업을 순서대로 승 or 무 or 패 인 경우의 백트래킹을 하면 된다.
시간 복잡도는 최악의 경우 3^15 번의 탐색을 진행한다. 그러나 가지치기를 잘한다면 거의 바로 찾을 수 있다.
💡 해법
각각의 매치업에서의 결과를 배열에 저장해도 된다. 하지만 너무 불편하다.
그렇다면 결과 상태를 빠르게 판단하는 방법을 찾고싶다. 바로 숫자로 담아놓으면 된다.
세팀의 결과가 만약 숫자 "ABC,XYZ,QWE" 라고 가정해보자.
ABC는 첫 팀의 승무패, XYZ는 두 번째 팀의 승무패인 셈이다.
ABC에서도 A는 승이고, B는 무, C는 패이다.
즉 1000단위 마다 100을 곱하면 승, 10을 곱하면 무, 1을 곱하면 패 자릿수이다.
5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4
-> 500,302,203,005,401,104
4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3
-> 410,302,410,113,005,113
5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5
-> 500,401,221,203,104,005
5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4
-> 500,311,212,203,005,104
와! 18개의 상태를 한 번에 판단하는 방법을 찾았다!
이제 가지치기를 할 때 저렇게 만든 숫자와 다르면 가지치기를 진행할 수 있게 된다!
자릿수 크기 순인 승,무,패 순으로 백트래킹을 해준다.
이렇게 내림차순으로 백트래킹하면 큰 자릿수부터 입력값과 값이 맞춰지면서 백트래킹이 된다.
따라서 유망하지 않은 결과값은 원래 입력값보다 큰 경우이다.
아 참고로 18자리이므로 long long 타입을 사용해야한다.
📕 C++ 풀이
result : 입력받은 승무패 결과를 long long에 담음
matchup : 두 국가간의 매치업들을 순서대로 15개 넣어놓은 배열
state : 승무패 상태 값
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll result;
ll r[6] = {1'000'000'000'000'000, 1'000'000'000'000, 1'000'000'000, 1'000'000, 1'000, 1};
int matchup[15][15] = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}};
void input(){
result = 0;
for (int j = 0; j < 18; j++){
int num;
cin >> num;
result = result * 10 + num;
}
}
bool solve(int n, ll state){
if (n == 15) return state == result;
if (state > result) return false;
int x = matchup[n][0], y = matchup[n][1];
ll win = state + 100 * r[x] + r[y];
ll draw = state + 10 * r[x] + 10 * r[y];
ll lose = state + r[x] + 100 * r[y];
return solve(n + 1, win) || solve(n + 1, draw) || solve(n + 1, lose);
}
void solution(){
for (int i = 0; i < 4; i++){
input();
cout << solve(0, 0) << ' ';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
solution();
}📗 Java 풀이
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringBuilder sb = new StringBuilder("");
static StringTokenizer st;
static long[] exp = {1_000_000_000_000_000L,1_000_000_000_000L,1_000_000_000L,1_000_000L,1_000L,1L};
static long result;
static int[][] matchUp = {{0,1},{0,2},{0,3},{0,4},{0,5},{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}};
public static void main(String[] args) throws IOException {
for(int tc=0;tc<4;tc++) {
result = Long.parseLong(br.readLine().replaceAll(" ", ""));
sb.append((solve(0,0)?"1":"0")+" ");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static boolean solve(int n, long state) {
if(n==15) return state == result;
if(state > result) return false;
boolean ret = false;
int A = matchUp[n][0], B = matchUp[n][1];
long win = state + 100*exp[A] + exp[B];
long draw = state + 10*exp[A]+10*exp[B];
long lose = state + exp[A] + 100*exp[B];
return solve(n+1,win) || solve(n+1,draw) || solve(n+1,lose);
}
}