[백준] 17281 - ⚾

1. 문제

17281번: ⚾

2. 개요

순열 + 완전탐색 문제.

3. 풀이 및 코드

3-1. 풀이

파이썬의 경우 itertools.permutation으로 순열을 날로먹을수 있어서 편하다.

처음에는 base라는 길이 7의 deque를 만들어서 루타만큼 회전시키고 4번 인덱스의 합만큼 점수를 늘리고 4번 인덱스 이후의 값들을 초기화하는 방법을 썼었는데 시간초과로 통과가 안돼서 단순하게 각 루타의 경우 베이스의 상황들을 만들어주는 방식으로 했다.

C#의 경우는 순열만 직접 만들고 이후는 같은 방식으로 해결했다.

Python

import sys
import itertools

N = int(sys.stdin.readline())

inningresult = []
for i in range(N):
    inningresult.append(list(map(int, sys.stdin.readline().split())))

ans = 0

for k in itertools.permutations([0, 1, 2, 3, 4, 5, 6, 7, 8]):
    if k[3] != 0:
        continue

    now = 0
    score = 0
    for inning in inningresult:
        first, second, third = 0, 0, 0
        outs = 0

        while outs < 3:
            if inning[k[now]] == 0:
                outs += 1
            elif inning[k[now]] == 1:
                score += third
                first, second, third = 1, first, second
            elif inning[k[now]] == 2:
                score += second + third
                first, second, third = 0, 1, first
            elif inning[k[now]] == 3:
                score += first + second + third
                first, second, third = 0, 0, 1
            elif inning[k[now]] == 4:
                score += 1 + first + second + third
                first, second, third = 0, 0, 0
                
            now = (now + 1) % 9

    ans = max(ans, score)

print(ans)

C#

class Program
{
    static int answer = 0;
    static List<int[]> lists = new List<int[]>();
    static List<List<int>> inningResult = new List<List<int>>();

    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());

        for (int i = 0; i < N; i++)
        {
            List<int> list = Array.ConvertAll(Console.ReadLine().Split(), int.Parse).ToList();
            inningResult.Add(list);
        }

        int[] array = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
        Perm(array, 0);

        Console.WriteLine(answer);
    }

    static void Perm(int[] array, int k)
    {
        if (k == array.Length - 1 && array[3] == 0)
        {
            baseball(array, inningResult);
        }
        else
        {
            for (int i = k; i < array.Length; i++)
            {
                int temp = array[k];
                array[k] = array[i];
                array[i] = temp;

                Perm(array, k + 1);
                temp = array[k];
                array[k] = array[i];
                array[i] = temp;
            }
        }
    }

    static void baseball(int[] array, List<List<int>> lists)
    {
        int now = 0;
        int score = 0;
        foreach (List<int> list in lists)
        {
            int first = 0;
            int second = 0;
            int third = 0;
            int outs = 0;

            while (outs < 3)
            {
                if (list[array[now]] == 0)
                    outs++;
                else if (list[array[now]] == 1)
                {
                    score += third;
                    third = second;
                    second = first;
                    first = 1;
                }
                else if (list[array[now]] == 2)
                {
                    score += second + third;
                    third = first;
                    second = 1;
                    first = 0;
                }
                else if (list[array[now]] == 3)
                {
                    score += first + second + third;
                    third = 1;
                    second = 0;
                    first = 0;
                }
                else if (list[array[now]] == 4)
                {
                    score += 1 + first + second + third;
                    third = 0;
                    second = 0;
                    first = 0;
                }

                now = (now + 1) % 9;
            }
        }

        answer = Math.Max(answer, score);
    }
}