Joonas' Note

Joonas' Note

BOJ 15685 - 드래곤 커브 본문

알고리즘/문제 풀이

BOJ 15685 - 드래곤 커브

2018. 4. 17. 16:56 joonas

    링크: 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 12755 - 수면 장애  (0) 2018.04.17
    BOJ 2022 - 사다리  (0) 2018.02.08
    알고리즘 공부 순서  (0) 2017.12.08
    Comments