[백준] 15685_드래곤 커브 (Python)

15685_드래곤 커브 (Python)

0. 출처

• 유형 : 시뮬레이션 (glod 4)
• 링크 : 15685번: 드래곤 커브

1. 기록

• 22/04/07 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

'''
1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

sample

(4) 정리

0 세대 - 0

1 세대 - 0 1

2 세대 - 0 1 2 1

3 세대 - 0 1 2 1 2 3 2 1

4 세대 - 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

다음 세대는 이전 세대의 '역방향'으로 +1 한 방향을 나타내게 된다. (문제에서 핵심이 되는 규칙성★)
(사람들이 이러한 규칙성을 봤다는게 신기함..)

또한 세대가 증가할 때, 선분의 갯수가 공비가 2인 등비 수열인 것을 파악할 수 있다.
이것으로 배열의 크기를 추측 및 설정할 수 있다.

단순 이중 반복문을 통해 네 꼭짓점이 드래곤 커브로 만들어졌는지 확인하면 된다.
주의할 점은 x, y 방향으로 벽에 도달했을 때는 탐색할 수 없다는 것이다.

(5) 참고

문제 이해1
문제 이해2