17281번 ⚾

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

삼성 boj 백준 SW역량테스트 시뮬레이션 구현 simulation 복습 필수 코딩 테스트 코테 추천 생각 논리 야구 시간초과 벡터

처음에는 문제의 예제 3과 4를 이해하기 어려웠다.

핵심은 

1. 직접 경기를 뛰는 타자의 '치는 순서'(선수의 번호가 아니다.)는 이닝이 바뀌어도 그 순서(치는 순서)는 유지한다.

2. 0번 선수는 3번 자리로 고정되어 있다.(문제에서는 1 ~ 9번 이지만, 0 ~ 8번으로 구현하였다.)

3. vector보다는 일반 배열이 훨씬 빠르다.

위의 3가지만 주의하면 풀 수 있다.

나는 첫 번째 제출에서 시간 초과를 받았다. 그 후 vector를 일반 배열로 바꾸어 제출하였더니 맞았다.

vector의 연산은 느리기 때문에 되도록 일반 배열을 활용하자.

특히, 크기를 미리 알 경우에는 일반 배열을 사용하자.

시간 초과

#include<bits/stdc++.h>
 
using namespace std;
 
int n, answer;
bool use[10];
vector<vector<int> > v;
 
int score(vector<int> &p, int result) {
    int ret = 0;
    vector<int> vp(5, 0);
 
    for (int i = 1; i <= 3; i++) {
        if (p[i]) {
            if (i + result >= 4) {
                ret += p[i];
            }
            else {
                vp[i + result] = p[i];
            }
        }
    }
 
    p = vp;
 
    return ret;
}
 
int simulation(vector<int> &order)
{
    int idx = 0, ret = 0, len = 1;
 
    for (auto e : v) {
        int out = 0;
        vector<int> p(5, 0); // 여기에 있어야 한다. for(auto e : v) 위에 있으면 안 됨.
 
        while (1)
        {
            int result = e[order[idx]];
 
            // Three Out 검사
            if (result == 0) {
                if (++idx == 9) {
                    idx = 0;
                }
                if (++out == 3) {
                    break;
                }
                continue;
            }
 
            // 한 번 칠 때 마다 점수 계산
            ret += score(p, result);
 
            if (result == 4) {
                ++ret;
            }
            else {
                ++p[result];
            }
 
            if (++idx == 9) {
                idx = 0;
            }
        }
    }
 
    return ret;
}
 
// 4 ~ 8번 자리 배정(3번 이후)
void After(int pos, vector<int> &order)
{
    if (pos == 9) {
        answer = max(answer, simulation(order));
        return;
    }
 
    for (int i = 1; i < 9; i++) {
        if (!use[i]) {
            use[i] = true;
            order[pos] = i;
 
            After(pos + 1, order);
 
            order[pos] = -1;
            use[i] = false;
        }
    }
}
 
// 0 ~ 2번 자리 배정(3번 이전)
void Before(int pos, vector<int> &order)
{
    if (pos == 3) {
        After(4, order);
        return;
    }
 
    for (int i = 1; i < 9; i++) {
        if (!use[i]) {
            use[i] = true;
            order[pos] = i;
 
            Before(pos + 1, order);
 
            order[pos] = -1;
            use[i] = false;
        }
    }
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        vector<int> temp;
        int input;
        for (int j = 0; j < 9; j++) {
            scanf("%d", &input);
            temp.push_back(input);
        }
        v.push_back(temp);
    }
 
    vector<int> v(9, -1);
    v[3] = 0;
 
    Before(0, v);
 
    printf("%d\n", answer);
 
    return 0;
}

정답

#include<bits/stdc++.h>
 
using namespace std;
 
int n, answer;
bool use[10];
vector<vector<int> > v;
 
// 칠 때 마다 점수 계산
int score(int *p, int result) {
    int ret = 0, vp[5] = { 0, 0, 0, 0, 0 };
 
    for (int i = 1; i <= 3; i++) {
        if (p[i]) {
            if (i + result >= 4) {
                // 홈으로 들어올 수 있다면
                ret += p[i];
            }
            else {
                // 그게 아니라면
                vp[i + result] = p[i];
            }
        }
    }
 
    // 갱신
    for (int i = 0; i < 5; i++) {
        p[i] = vp[i];
    }
 
    return ret;
}
 
int simulation(vector<int> &order)
{
    int idx = 0, ret = 0;
 
    // 모든 이닝을 살펴본다
    for (auto e : v) {
        int out = 0;
        int p[5] = { 0, 0, 0, 0, 0 };
 
        while (1)
        {
            int result = e[order[idx]];
 
            // Three Out 검사
            if (result == 0) {
                // 다음 선수
                if (++idx == 9) {
                    idx = 0;
                }
                // Three Out이면 끝
                if (++out == 3) {
                    break;
                }
                continue;
            }        
 
            // 칠 때 마다 점수 계산
            ret += score(p, result);
 
            // 홈런이라면
            if (result == 4) {
                // 친 선수도 미리 계산
                ++ret;
            }
            else {
                // 그게 아니라면 친 곳 1 증가
                ++p[result];
            }
            
            // 다음 선수
            if (++idx == 9) {
                idx = 0;
            }
        }
    }
 
    return ret;
}
 
// 4 ~ 8번 자리를 채운다.(3번 자리 이후)
void After(int pos, vector<int> &order)
{
    if (pos == 9) {
        // 최댓 값
        answer = max(answer, simulation(order));
        return;
    }
 
    for (int i = 1; i < 9; i++) {
        if (!use[i]) {
            use[i] = true;
            order[pos] = i;
 
            After(pos + 1, order);
 
            order[pos] = -1;
            use[i] = false;
        }
    }
}
 
// 0 ~ 2번 자리를 먼저 채운다.(3번 자리 이전)
void Before(int pos, vector<int> &order)
{
    if (pos == 3) {
        After(4, order); // 3번 자리는 이미 0번 선수가 차지.
        return;
    }
 
    for (int i = 1; i < 9; i++) {
        if (!use[i]) {
            use[i] = true;
            order[pos] = i;
 
            Before(pos + 1, order);
 
            order[pos] = -1;
            use[i] = false;
        }
    }
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        vector<int> temp;
        int input;
        for (int j = 0; j < 9; j++) {
            scanf("%d", &input);
            temp.push_back(input);
        }
        v.push_back(temp);
    }
 
    vector<int> v(9, -1);
    v[3] = 0; // 3번 자리는 0번 선수가 쳐야한다.
 
    Before(0, v);
 
    printf("%d\n", answer);
 
    return 0;
}