끄적끄적 코딩
article thumbnail
728x90

시뮬레이션 문제입니다.

N개의 드래곤 커브가 (x,y)좌표에서 D방향으로 G레벨로 있을 때
네 꼭짓점이 드래곤 커브의 일부인 1x1 크기의 정사각형의 개수를 구하는 문제입니다.

다음의 규칙들을 이용해서 문제를 해결했습니다.

드래곤 커브의 N레벨은
드래곤 커브의 N-1레벨과 드래곤 커브의 N-1레벨의 모양을 90도를 한 것을 끝에 붙인 모양입니다.
고로 드래곤 커브는 2^n개의 선분을 가지게 됩니다.

드래곤 커브는 시작지점은 다르지만 결국 패턴은 방향에 따른 4가지 밖에 없습니다.
그래서 4가지 패턴에 대해서 전부 배열에 넣어두고
각 레벨에 따라서 패턴의 횟수를 실행시켜줬습니다.

이렇게 실행시키면서 체크된 (x, y)좌표는 체크를 해두고
모든 실행이 끝났을 때 정사각형인지 체크를 하면 됩니다.

 

 

<c++ />
#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <string> using namespace std; bool map[110][110]; int pattern[4][2049]; int quo[11] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 }; int change(int num) { switch (num) { case 0: num = 1; break; case 1: num = 2; break; case 2: num = 3; break; case 3: num = 0; break; } return num; } void SetPattern() { pattern[0][0] = 0; //우 pattern[1][0] = 1; //상 pattern[2][0] = 2; //좌 pattern[3][0] = 3; //하 for (int i = 0; i < 4; ++i) { for (int j = 0; j < 11; ++j) { for (int k = 0; k < quo[j]; ++k) { pattern[i][quo[j] + k] = change(pattern[i][quo[j] - k - 1]); } } } } void run(int x, int y, int d, int g) { map[y][x] = true; for (int i = 0; i < quo[g]; ++i) { switch (pattern[d][i]) { case 0: ++x; break; case 1: --y; break; case 2: --x; break; case 3: ++y; break; } map[y][x] = true; } } void find() { int count = 0; for (int i = 0; i < 101; ++i) { for (int j = 0; j < 101; ++j) { if (map[i][j] & map[i + 1][j] & map[i][j + 1] & map[i + 1][j + 1]) { ++count; } } } cout << count << endl; } int main(int argc, char* argv[]) { memset(map, false, sizeof(map)); SetPattern(); int n; int x, y, d, g; cin >> n; for (int i = 0; i < n; ++i) { cin >> x >> y >> d >> g; run(x, y, d, g); } find(); return 0; }

검색 태그