백준 17281. ⚾ (순열, 구현)

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

17281번: ⚾

순열을 이용한 구현 문제이다.

요새 dp 문제를 계속 풀고 있어서, next_permutataion으로 풀어야하는 문제인지 규칙이 있는데 못찾은 dp 문제인지 엄청 고민했다...... 

이문제는 8!(40320) * 50(n, n <= 50) * 27 (9명중 아웃을 내는 선수가 1명인 경우 대략 27번 공을 쳐야함.)의 시간복잡도를 가져서 5000만번 연산하므로 next_permutation이 가능하다. 

 

1. 특징

1) 실수할 곳이 많은 구현 문제

 

2. 삽질 포인트

작성한 대부분의 파트에서 다 실수를 해서 시간이 오래 걸렸다. 

1) vector에 2~9번 선수를 넣고, next_permutation(vec.begin(), vec.end()); 을 돌면서 선수의 순서를 바꿔주었다. 그리고 do while문 안에서 vec[3] = 1번 선수를 넣어줬다. next_permutation을 도는 과정에서 vector를 임의로 바꾸는 작업을 해서 에러가 발생했다. 

2) cnt(out값을 나타내는 변수) <= 3이면 while문을 나가게 설정했다. -> cnt <3이어야함! 

3) 루에 있는 선수들을 회전시키는 함수에서, 안타 2루타 3루타일 때와 홈런일 때를 따로 처리해주었다. 

이때, if(안타 && 2루타 && 3루타) 일 때라고 코드를 작성했다. -> if(안타 || 2루타 || 3루타)이어야 함.

4) 나는 각 루 배열에 선수의 index번호(선수들의 번호 - 1 )를 넣었다.( 1번루에 3번 선수가 있다면 ru[0] = 2;

그리고 루 배열을 0으로 초기화했다. 루 원소가 0이라면 선수가 없다고 판별했다.  

문제는 1번째 선수는 배열에 0이 들어가게 되는데, 따라서 1번째 선수가 있어도 선수가 없다고 판별했다. 

-> ru를 -1로 초기화함.

5) 루에 있는 선수들을 회전시키는 함수에서, 선수들이 다음 루로 이동하면, 현재 있던 루는 더이상 그선수가 없음을 처리해주어야하는데 안해주어서 오류가 났다. -> ru[i] = -1로 처리

6) 타자가 안타, 2루타, 3루타를 쳤을 때, 어디로 갈 수 있는지에 대한 처리를 잘못해주었다. 안타, 2루타, 3루타에 상관없이 타자를 1루에 위치하게 설정해서 오류가 났다(ru[0]에 선수 배치) -> ru[결과-1]에 선수 배치

 

3. 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int arr[52][10];
int ru[3]; // 0: 1루, 1:2루, 2:3루
vector<int> _vec; //타자 순서

int ans;
int CalRu(int gap, int num) //결과, 지금결과를 낸 사람의 선수번호
{
    int score = 0;

    if(gap == 1 || gap == 2 || gap == 3)
    {
        for(int i = 2; i >= 0; i--)
        {
            if(ru[i] != -1) //사람이 있으면
            {
                if(i+ gap > 2)
                {
                    ru[i] = -1;
                    score+=1;
                }
                else
                {
                    ru[i+gap] = ru[i];
                    ru[i] = -1;
                }
            }
            
        }
        ru[gap-1] = num;     
    }
    if(gap == 4)
    {
        score = 1;
        for(int i = 2; i >= 0; i--)
        {
            if(ru[i] != -1) //사람이 있으면
            {
                score +=1;
                ru[i] = -1;
            }
        }
    }
    return score;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for(int i = 0; i < n; i++) // 이닝별
    {
        for(int j = 0; j < 9; j++)
        {
            cin >> arr[i][j]; // 선수들이 치는 점수
        }
    }

    _vec = {2,3,4,5,6,7,8,9};

    do
    {
        vector<int> tmp(_vec);
        tmp.insert(tmp.begin()+3, 1);

        int curvalue = 0;
        int j = 0;
        for(int i = 0; i < n; i++) //i번째 이닝에서 얻은 점수
        {
            int cnt = 0; // 아웃수
            //j = 0; //타자를 치는 사람의 인덱스
            //새 이닝이 시작되면 루에 서있는 사람 없어야함
            fill(ru, ru+3, -1);
            while(cnt < 3) //out이 3번이상이 되면 빠져나감
            {
                int curv = arr[i][tmp[j]-1]; // 타자에 선 사람이 친 결과
                int curnum = tmp[j];
                j++;
                if(j==9) j = 0; // 마지막 사람이 치면 다시 앞으로 돌아옴
                if(curv != 0)
                {                  
                    curvalue += CalRu(curv, curnum);
                }
                else cnt++;
            }
           
        }

        ans = max(ans, curvalue);

    }while(next_permutation(_vec.begin(), _vec.end()));
    
    cout << ans;
   
}