티스토리 뷰
사다리 게임에 주어진 사다리에 가로선을 추가하여 i번째 사다리 게임의 결과가 i가 나오도록 하는 문제이다.
문제 자체는 백트래킹 알고리즘으로 간단히 해결할 수 있다. 하지만 시간, 메모리 제한을 고려하여 최적화 해야한다.
사다리를 배열로 치환하고 (r, c)에 사다리가 있을 경우 1 또는 True, 없을 경우 0 또는 False로 표시한다. 그리고 사다리를 놓으며 따라 내려간다. 만약 i가 (i, c)에서 사다리를 만날 경우 i = i + 1, (i-1, c)에서 만날경우 i = i - 1을 수행한다.
반복마다 사다리를 타고 내려가 임의의 i에 대해서 결과가 i가 나오는지 확인한다.
728x90
'PS > 백준' 카테고리의 다른 글
| [백준] 15686 치킨 배달 (0) | 2021.03.12 |
|---|---|
| [백준] 15685 드래곤 커브 (0) | 2021.03.11 |
| [백준] 15683 감시 (0) | 2021.03.09 |
| [백준] 9663 N-Queen (0) | 2021.03.03 |
| [백준] 12100 2048(Easy) (0) | 2021.03.02 |
댓글