[백준] 17281 야구?

문제의 출처는 아래와 같다.

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

 

삼성 A형 기출문제 문제집에 야구공 모양의 문제이다.

 

이 문제는 처음에 아무리봐도 이해가 잘 되지 않았다. 그래서 처음에 해설을 참고할 수 밖에 없었다.

 

이 문제는 

1) 순열을 통해 전체 경우를 찾는데, 4번타자는 항상 처음에 배치되는 조건을 만든다.

2) 야구의 규칙대로 구현을 한다.

 

인데 각 줄에 있는것이 무슨 의미인지 이해를 못했다. 각 줄은 1~n 이닝이니 순서와 상관이 없다. 우리는 순열을 사용해서 3아웃이 되면 다음 이닝에 따른 값을 사용하면 되는 문제이다....

 

구현부분은 잘 작성이 안되어서 해설코드를 그대로 참고하여 내 코드에 맞게 조금만 수정하였다. 

 

문제는 처음에 순열을 next_permutation() 으로 했는데 계속 시간초과가 발생해서.. 재귀함수로 바꾸어 하니 문제없이 해결되었다. next_permutation()을 사용한 정답 코드를 아무리봐도 내가 작성한 순열 코드와 차이점이 없는데 뭔가 좀 이상하다. 

 

어찌됐든, 오랜만에 문제를 풀어볼 기회였다.

 

#include<stdio.h>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int n, arr[55][9],order[9],pos[10],ans,visit[9];
int player[10];
 
void play() {
    int out, cur = 0, point = 0; 
    for (int i = 0; i < n; i++) {
        out = 0; 
        bool base[4] = { 0,0,0,0 }; 
        while (out<3) { 
            int b = player[cur]; 
            base[0] = true; 
            if (arr[i][b] == 0) out++; 
            else {
                for (int j = 3; j >= 0; j--) { 
                    if (base[j] == false) continue;
                    int k = j + arr[i][b]; 
                    if (k>3) point++; 
                    else base[k] = true; 
                    base[j] = false; 
                }
            }
            cur++; 
            if (cur == 9) cur = 0; 
        }
    }
    ans = max(point, ans);
}
 
void dfs(int a) {
    if (a == 9) {
        if (player[3] != 0) return;
        //for (int i = 0; i < 9; i++) {
            //printf("%d ", player[i]);
        //}
        //printf("\n");
        play();
        return;
    }
    for (int i = 0; i < 9; i++) {
        if (visit[i] == 0) {
            visit[i] = 1;
            player[a] = i;
            dfs(a + 1);
            visit[i] = 0;
        }
    }
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 9; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    dfs(0);
    printf("%d", ans);
    return 0;
}