17281번: ⚾
⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종
www.acmicpc.net
시뮬레이션, 브루트포스 문제이다.
문제 설명은 현행 야구 규칙과 동일하다.
주어지는 이닝은 모두 공격일 때의 타자 정보이므로, 수비는 생각하지 않아도 된다.
문제 하단에 pypy3 1.5초라고 명시돼 있는 것이 매우 싸늘한 분위기를 자아낸다...
파이썬으로는 택도 없다는 소리이기 때문이다.
시간초과를 잡기 위해 처음 코드에서 다음과 같은 사항을 고쳤다.
- 진루 상황을 저장하는 변수: 정수 → 리스트 → 정수
- 하나의 타순에 대해 점수 계산하는 전체 코드: 평문 → 함수
- 진루 상황에 따라 점수 누적하는 부분: 반복문 -> if문
1번이 제일 컸다..
처음에 그냥 정수로 줄줄이 쓰다가 깔끔하게 반복문으로 쓰고 싶어서 리스트로 바꿔서 다시 구현했더니 시간초과가 났다..ㅠ
from itertools import permutations
import sys
read = lambda: sys.stdin.readline().strip()
n = int(read())
innings = [list(map(int, read().split())) for _ in range(n)]
ans = 0
def play(batters):
score = 0
idx = -1
for inning in innings:
out_cnt = 3
b1, b2, b3 = 0, 0, 0
while out_cnt > 0:
idx = (idx + 1) % 9
# cur_bat = inning[batters[idx]] # 이 부분도 시간을 절약할 수 있다.
if inning[batters[idx]] == 0: # cur_bat으로 다 바꿔도 통과는 된다.
out_cnt -= 1
elif inning[batters[idx]] == 1:
score += b3
b1, b2, b3 = 1, b1, b2
elif inning[batters[idx]] == 2:
score += b2 + b3
b1, b2, b3 = 0, 1, b1
elif inning[batters[idx]] == 3:
score += b1 + b2 + b3
b1, b2, b3 = 0, 0, 1
else:
score += b1 + b2 + b3 + 1
b1, b2, b3 = 0, 0, 0
return score
orders = permutations([i for i in range(1, 9)], 8)
for order in orders:
order = list(order)
batters = order[:3] + [0] + order[3:]
score = play(batters)
if ans < score: # max, min 구문보다 시간을 절약할 수 있다.
ans = score
print(ans)
'Algorithm > Simulation' 카테고리의 다른 글
| [프로그래머스 Programmers] 괄호 변환 (Python) (0) | 2021.03.26 |
|---|---|
| [프로그래머스] 셔틀버스 (Python) (0) | 2020.11.11 |