반응형
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
내 풀이방법은 Python 3에서 시간초과를, PyPy3에서는 통과했다.
테트로미노의 저 다섯 가지 shape를 어떤 식으로 정의했느냐에 따라 다른 것 같은데,
리스트로 정의한 뒤 rotate 함수를 적용한 내 방식이 시간초과를 불러일으킨 것 같다.
아예 가능한 모든 shape의 좌표를, 리스트보다 효율적인 자료구조를 써서 작업하면 python 3으로도 통과하는 것 같다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 2018 카카오 recruit - 프렌즈4블록 (Level 2) (0) | 2020.03.07 |
|---|---|
| [Python] 백준 1890. 점프 (0) | 2020.03.05 |
| [Python] 프로그래머스. 2018 카카오 recruit - 압축 (Level 2) (0) | 2020.03.03 |
| [Python] 백준 11724. 연결 요소의 개수 (1) | 2020.03.02 |
| [Python] 백준 17471. 게리맨더링 (0) | 2020.02.29 |