BOJ 15685 - 드래곤 커브

링크: https://www.acmicpc.net/problem/15685

문제

알고스팟의 JM북에 그려진 그 드래곤 커브가 맞다. 

간단한 수학 규칙으로 그려지는 그림인데, 이 문제에서는 드래곤 커브가 네 꼭지점을 모두 지나는 칸이 몇 개인지 구하는 거였다.

풀이

드래곤 커브의 규칙을 미리 만들어놓고, 드래곤 커브의 시작점과 시작 방향이 주어졌을 때 규칙에 맞게 이동하면서 주변 칸에 해당 꼭지점이 지나갔음을 기록한다.

드래곤 커브는 이전 세대의 드래곤 커브를 이용하기 때문에 반복적인 구조이다. 각 방향과 관련된 변수들을 잘 설정하면 쉽게 구현할 수 있다. 나는 문제에 맞춰 우,상,좌,하 순서로 0,1,2,3을 사용했다.

원소들은 진행 방향, 드래곤 커브를 \(G_0 = \{\dots, a, b, c, d\}\) 이라 하자. 이 커브를 전체 90도 회전하는 것은 각 원소들을 모두 90도 회전한 것과 같다. 즉, \(G_0\)을 90도 회전한 수열 \(G_0' = \{\dots, a', b', c', d'\}\) 이다.

이전 세대를 수열 \(G_0\)라고 하면 다음 세대의 드래곤 커브는 \(G_1 = G_0' + G_0\) 로 전개된다.

0세대부터 10세대까지 미리 구하는 코드는 굉장히 단순하다.

드래곤 커브는 선분, 우리가 확인해야 하는 것은 칸이기 때문에 드래곤 커브가 어떤 점 \((y, x)\)를 지날 때마다, 주변 4칸에 잘 기록하면 된다.

코드

반응형

• 카카오스토리
• 트위터
• 페이스북

'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 3075 - Astromeeting  (0)	2018.04.18
BOJ 15656 - 치킨 배달  (0)	2018.04.17
BOJ 15685 - 드래곤 커브  (0)	2018.04.17
BOJ 12755 - 수면 장애  (0)	2018.04.17
BOJ 2022 - 사다리  (0)	2018.02.08
알고리즘 공부 순서  (0)	2017.12.08