[C] 백준 17281번 : ⚾

문제

 

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다.

두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다.

공격은 투수가 던진 공을 타석에 있는 타자가 치는 것이다. 공격 팀의 선수가 1루, 2루, 3루를 거쳐서 홈에 도착하면 1점을 득점한다. 타자가 홈에 도착하지 못하고 1루, 2루, 3루 중 하나에 머물러있을 수 있다. 루에 있는 선수를 주자라고 한다. 이닝이 시작될 때는 주자는 없다.

타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 각각이 발생했을 때, 벌어지는 일은 다음과 같다.

• 안타: 타자와 모든 주자가 한 루씩 진루한다.
• 2루타: 타자와 모든 주자가 두 루씩 진루한다.
• 3루타: 타자와 모든 주자가 세 루씩 진루한다.
• 홈런: 타자와 모든 주자가 홈까지 진루한다.
• 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.

한 야구팀의 감독 아인타는 타순을 정하려고 한다. 아인타 팀의 선수는 총 9명이 있고, 1번부터 9번까지 번호가 매겨져 있다. 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자.

 

입력

 

첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다.

• 안타: 1
• 2루타: 2
• 3루타: 3
• 홈런: 4
• 아웃: 0

각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.

 

출력

 

아인타팀이 얻을 수 있는 최대 점수를 출력한다.

 

풀이

 

#include <stdio.h>
 
int score[55][10];
int arr[8] = {2,3,4,5,6,7,8,9};
int max_point = -1;
int N;
 
void swap(int *a, int *b ){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
 
int get_point(){
    int order[9]={arr[0],arr[1],arr[2],1,arr[3],arr[4],arr[5],arr[6],arr[7]};
    int inning = 0;
    int idx = 0;
    int point = 0;
    while(1){
        if(inning==N) break;
        int out = 0;
        int ground[4] = {0,};
        while(out<3){
            if(score[inning][order[idx]-1]==0) out++;
            else{
                for(int t = 0 ; t < score[inning][order[idx]-1] ; t++){
                    if(ground[3]!=0) point++;
                    ground[3]=ground[2];
                    ground[2]=ground[1];
                    if(t==0) ground[1]=1;
                    else ground[1] = 0;
                }
            }
            idx = (idx+1)%9;
        }
        inning++;
    }
    return point;
}
 
void permutation(int n, int r){
    if( r == 0){
        int point = get_point();
        if(point>max_point) max_point = point;
        return;
    }
 
    for(int i=n-1; i>=0; i--){
        swap(&arr[i], &arr[n-1]);
        permutation(n-1, r-1);
        swap(&arr[i], &arr[n-1]);
    }
 
}
 
int main() {
    scanf("%d",&N);
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < 9 ; j++){
            scanf("%d",&score[i][j]);
        }
    }
    permutation(8,8);
    printf("%d\n",max_point);
    return 0;
}
 
 

 

삼성 SW 역량 테스트 기출 문제!

순열을 이용하여 모든 타순을 구하고 각 타순별로 얻을 수 있는 점수를 구해 최대 점수를 찾는 방식으로 코드를 작성하였다

순열 코드를 기본으로 두고 순열 재귀함수에서 r==0인 경우, 즉 arr 상태가 유일한 순서인 경우마다 점수를 계산해주었다

 

점수를 구하는 함수는 get_point 함수를 구현해보았다

이때 순열로 얻어낸 순서와 별개로 4번 타자는 항상 1번 선수이므로 그 점을 고려하여 새로운 순서를 만들어 order 배열에 저장해주었다

이중 while문 구조를 사용하였는데 처음 while문은 이닝이 끝날 때 까지를 나타내고 내부의 while문은 쓰리아웃이 나올때까지 반복되는 부분이다

야구장의 그라운드는 ground 배열을 사용하여 나타내어주었다

선수가 있는 그라운드는 1 없는 그라운드는 0의 값을 저장한다

안타가 나면 몇루타인지 확인하여 그만큼 선수들을 이동시켜주었다

이때 홈으로 선수가 들어오면 (ground[3]!=0) 점수를 증가시켜주었고, 2루타 이상이면 두번째부터는 선수가 처음만 이동하게 해주었다

점수를 구하는 함수는 알고리즘적인 개념 없이 정말 선수들이 어떻게 이동하는지를 머리속에서 그려가며 코드를 작성하였다

 

순열 함수만 잘 알고 있다면 쉽게 풀 수 있는 문제인것같다

순열 함수를 아직도 완전 편하게 쓸 수가 없고 늘 헷갈려서 순열 함수 연습 열심히 해야겠다