Joonas' Note

Joonas' Note

BOJ 11447 - Colby’s Costly Collectibles 본문

알고리즘/문제 풀이

BOJ 11447 - Colby’s Costly Collectibles

2019. 3. 11. 15:20 joonas

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

    문제

    문제에서 정의되는 x, y, z 방향으로 1000을 넘지 않는 길이만큼 C번 움직인 후에,
    마지막에 완성된 그림 속에 채워지는 삼각형의 수는 몇 개인지 맞추는 문제이다.

    삼각형들은 빈 공간이 없이 빽빽하게 채워져있고, 다시 시작점으로 돌아오지 않는 잘못된 입력은 주어지지 않는다.


    처음에는 x,y,z 방향을 2차원 x,y 평면으로 적당히 전사시켜서 그 넓이를 구하는 방식으로 해야하나? 라는 생각을 했다. 그 외에도 문제를 변형시키는 별 생각을 다 했는데 결국 풀이는 다각형의 면적을 구하는 문제였다.

    풀이

    다각형을 이루는 꼭짓점들이 주어지면, 그 다각형의 면적을 구하는 문제이다.


    이건 신발끈 공식으로 해결할 수 있다. 다각형의 각 꼭짓점의 좌표를 이용해서 그 면적을 구하는 방법이다.

    각 꼭짓점의 좌표를 \(x_i, y_i\)라고 하면 정의는 위와 같다. 우선 식의 정의만 보면 어려워보이지만 아래의 그림처럼 묶이기 때문에 생각보다 쉽다. 그 모양이 신발끈을 닮은 게 이름의 유래다.


    문제는 각 꼭짓점들을 구하는 것인데, 문제에서는 \(x, y, z\) 방향을 아래 그림처럼 정의하고 있고

    한 변의 길이를 1이라고 정했을 때, 방향 벡터 \(x\)는 \((1, 0)\)이라고 할 수 있다. 문제는 \(y\)와 \(z\)인데



    정삼각형이므로 왼쪽 그림과 같이 \(y\) 방향으로 가는 벡터는 \((0.5, sin{60^\circ}\))이다. 나머지 방향들도 같은 방식으로 모두 구할 수 있다.


    따라서 입력에서 x, y, z 방향이 주어질 때 마다 해당 벡터만큼 점을 이동시키면서 각 꼭짓점들을 모두 저장한다.

    하지만 이렇게 구해진 꼭짓점들을 사용해서 면적을 구한다면, 한 변의 길이가 1인 삼각형으로 가정하고 구한 것이므로 보정이 필요하다.

    면적을 구한 후 세 변의 크기가 1짜리인 삼각형의 크기로 나눈 이유가 그것이다.

    코드

    비슷한 문제


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

    BOJ 2096 - 내려가기  (0) 2019.03.13
    BOJ 16964 - DFS 스페셜 저지  (0) 2019.03.12
    BOJ 1976 - 여행 가자  (0) 2019.03.08
    BOJ 1613 - 역사  (0) 2019.02.24
    BOJ 9465 - 스티커  (0) 2019.02.24
    Comments