반응형
https://www.acmicpc.net/problem/17281
17281번: ⚾
⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에
www.acmicpc.net
삼성A형 기출문제였고, 효율성을 고려하면 백준 환경에서 python 3으로는 사실상 풀 수 없는 문제.
1번 타자는 정해져 있고, 나머지 8명의 타자에게 타순을 부여하는 문제이므로
완전탐색이고, 총 탐색해야 할 가짓수는 8!으로 약 4만 개 정도다.
python3 설정으로는 시간초과를 절대 해결할 수 없었고, pypy3을 써도 정말 간신히 통과한다.
정말 어떻게 풀어도 시간초과가 해결이 안 나서, 검색으로 찾은 C++ 코드로 통과한 다음 pypy3 통과자들의 코드를 봤는데,
변수 할당 하나 때문에 91%에서 시간초과가 계속 났던 거였다.
원래는 base를 의미하는 b1, b2, b3도 배열로 선언한 다음 for문으로 체크하도록 코드를 짰었는데,
이 정도로 빡빡한 조건에서는 사치였다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 백준 2110. 공유기 설치 (0) | 2020.02.13 |
|---|---|
| [Python] 프로그래머스. 영어 끝말잇기 (Level 2) (0) | 2020.02.12 |
| [Python] 백준 1021. 회전하는 큐 (0) | 2020.02.10 |
| [Python] 프로그래머스. 예산 (Level 3) (0) | 2020.02.08 |
| [Python] 백준 15997. 승부 예측 (카카오 코드페스티벌 2018) (0) | 2020.02.07 |