[백준] 17281 ⚾

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

1번 선수는 4번 타자로 정해져 있고, 나머지 선수들은 순서가 정해져 있지 않아 선수들이 갈 수 있는 모든 순서를 구해야 했습니다.

완전 탐색을 이용하여 가능한 모든 경우를 구하였고, 각 경우마다 이닝을 시뮬레이션하여 득점 가능한 점수들을 구하였습니다.

 

각 이닝을 시뮬레이션하는 로직에서 1루, 2루, 3루를 리스트로 관리하였고, 반복문을 이용하여 안타, 2루타, 3루타, 홈런의 경우에 모두 적용이 가능하도록 구현하였습니다.

그러나 문제에서 주어진 제한된 시간에 통과하지 못하였습니다.

 

이후 관련 내용에 대하여 찾아보니 Python3 으로 통과하기에는 거의 불가능하고, PyPy3 에서도 베이스를 리스트로 관리하면 시간 제한에 걸린다는 사실을 알게 되었습니다.

그리하여 리스트로 관리하던 베이스를 모두 각각의 변수로 바꾸었고, 조건으로 모두 구분하여 수동으로 베이스 정보를 수정하도록 구현하였습니다.

2) 알고리즘

• 완전탐색

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def solution(n):                        # 타자 순서 정하는 함수
    if n == 9:                          # 9번 타자까지 모두 순서를 정했다면
        inning(0, 0, 0)                 # 시뮬레이션 시작
        return
    
    for i in range(9):
        if number_player[i] == -1:      # 현재 순번에 타자가 없다면
            number_player[i] = n        # 타자 순번 지정
            solution(n+1)               # 다음 타자의 순번 정하기
            number_player[i] = -1

def inning(n, ans, turn):               # 이닝 시뮬레이션 함수 (이닝 번호, 현재까지 점수, 현재 순서)
    global answer

    if n == N:
        answer = max(answer, ans)       # 높은 점수 저장
        return

    score, remain_out, base1, base2, base3 = 0, 3, 0, 0, 0      # 현재 이닝의 점수, 남은 아웃 카운트, 1루, 2루, 3루
    while remain_out > 0:                               # 아웃 카운트 남았으면 진행
        player = number_player[turn]                    # 현재 순서인 선수

        if not scores[n][player]:                       # 아웃이라면, 아웃카운트 증가
            remain_out -= 1                             
        elif scores[n][player] == 1:                    # 안타라면, 3루 점수 득점
            score += base3                              # 각 1루씩 전진
            base1, base2, base3 = 1, base1, base2
        elif scores[n][player] == 2:                    # 2루타라면, 2루, 3루 점수 득점
            score += base2 + base3                      # 각 2루씩 전진
            base1, base2, base3 = 0, 1, base1
        elif scores[n][player] == 3:                    # 3루타라면, 1,2,3루 점수 득점
            score += base1 + base2 + base3              # 각 3루씩 전진
            base1, base2, base3 = 0, 0, 1
        elif scores[n][player] == 4:                    # 홈런이라면 타자 및 모든 주자 득점
            score += base1 + base2 + base3 + 1          # 1,2,3루 모두 비어있게 설정
            base1, base2, base3 = 0, 0, 0

        turn = (turn + 1) % 9                           # 턴 증가
    
    inning(n+1, ans+score, turn)                        # 다음 이닝 진행

N = int(sys.stdin.readline())                                               # 이닝 수
scores = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]   # 이닝별 선수들 타자 정보
number_player = [-1] * 9                                                    # 타순별 선수 번호
number_player[3] = 0                                                        # 1번 타자는 4번 타자로 고정
answer = 0

solution(1)                     # 2번 타자부터 타순 정하기

print(answer)

---

🔗 문제 링크

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

17281번: ⚾

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다