어떻게 풀까?
이 문제에서 문제를 풀기위해 생각해봐야 할 것이 2 가지 있습니다.
1. 세대가 올라갈때 선을 어떻게 연결할 것인가?
2. 네 꼭짓점이 드래곤 커브의 일부인 것은 어떻게 찾을 것인가?
1번부터 시작하겠습니다.
우선, 예제를 하나 보시죠!
(0,0)에서 3 세대인 그래프입니다.
일단, 선의 총 길이를 보겠습니다.
선의 길이는 이전 세대의 길이만큼 +됩니다!
n-1 세대 길이가 x 였다면, n세대의 선분 길이는 총 2*x가 되는 것이죠!
즉, 2의 제곱승으로 길이가 늘어납니다.
문제에서 최대 세대가 10세대까지이므로, 길이는 총 1024까지 될 것 입니다!
그럼 가장 중요한 점!
과연, n-1세대에서 n세대로 갈 때 어떻게 그려야 하는가? 입니다.
저 위의 그림에서 한 번 어떻게 그려야하는지 생각해 봅시다!
시작 위치는 (0,0)이고 처음 방향은 오른쪽 입니다!
2세대의 끝 점은 (0,-2) 입니다.
그리고 잘 보시면, (0,0) ~ (0,-2)로 이어지는 점까지의 도형을 단순하게 시계 방향으로 돌리면 (0,-2) ~ (-2, -2)로 움직이는 지점과 똑같음을 볼 수 있습니다!
즉, 우상좌상으로 이어지는 선분 각각을 시계 방향으로 90도를 돌리면, 우 -> 하, 상 -> 우, 좌 ->상, 상-> 우가 되죠.
즉, 하우상우가 됩니다.
그렇다면, 끝 점인 (-2,-2)에서 하우상우를 하면 2세대 드래곤 커브의 끝점인 (0,-2)로 이동할 수 있다는 것 입니다.
그럼 여기서 3세대 드래곤을 그리는 방법은 무엇일까요?
하우상우를 뒤에서부터 180도 반대로 그리면 됩니다!
결국, 시계 방향으로 90도 돌린 뒤에 180도를 또 돌리므로, 총 270도를 돌리는 것입니다.
즉, 우상좌상을 뒤에서부터 반시계 방향으로 90도 돌려서 그리면 된다는 말이죠!!!
우상좌상 -> 상좌상우 -> 좌하좌상 이 되는 것이죠!
처음부터 끝까지 그리는 방법은
'우상좌상좌하좌상'이 되는 것입니다!
이 정보를 또 다시 배열에 저장해서 다음 세대 드래곤을 그릴때 이용하면 됩니다!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | const int dr[4] = { 0,-1,0,1 }; const int dc[4] = { 1,0,-1,0 }; const int inv[4] = { 1,2,3,0 }; cod dragon[20]; int direct[20][1024]; int sede[20]; int n; void makeDragon(int nD, int sede) { int nowLength = 1; for (int i = 0; i < sede; i++) { for (int j = nowLength - 1; j >= 0; j--) { int dir = inv[direct[nD][j]]; direct[nD][nowLength++] = dir; dragon[nD].r += dr[dir]; dragon[nD].c += dc[dir]; map[dragon[nD].r][dragon[nD].c] = 1; } } } | cs |
그렇다면, 이제 4개의 꼭짓점이 모두 드래곤 커브의 일부인지 확인하는 법에 대해서 생각해 봅시다.
우선 맵의 크기는 (0,0) ~ (100,100) 까지 존재합니다.
어짜피 좌표가 101*101개 까지이므로, 충분히 2차원 배열로 표현할 수 있는 범위입니다.
단순하게, 드래곤 커브에서 (x,y)의 점을 그리면, 맵에 1로 체크한 뒤에,
(0,0) ~ (100,100)까지 현재 자신의 좌표 (x,y)와 (x,y+1), (x+1,y), (x+1,y+1)이 모두 1 인지 확인해서 결과값에 더해주면 정답을 구할 수 있습니다!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | const int checkR[4] = { 0,0,1,1 }; const int checkC[4] = { 0,1,0,1 }; int getSagack() { for (int i = 0; i < n; i++) { makeDragon(i, sede[i]); } int res = 0; for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { int cnt = 0; for (int d = 0; d < 4; d++) { cnt += map[i + checkR[d]][j + checkC[d]]; } res += cnt >> 2; } } return res; } | cs |
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | #include<iostream> #include<cstring> using namespace std; struct DragonCurveInfo { int map[101][101]; typedef struct Cod { int r, c; } cod; const int dr[4] = { 0,-1,0,1 }; const int dc[4] = { 1,0,-1,0 }; const int inv[4] = { 1,2,3,0 }; const int checkR[4] = { 0,0,1,1 }; const int checkC[4] = { 0,1,0,1 }; cod dragon[20]; int direct[20][1024]; int sede[20]; int n; int getSagack() { for (int i = 0; i < n; i++) { makeDragon(i, sede[i]); } int res = 0; for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { int cnt = 0; for (int d = 0; d < 4; d++) { cnt += map[i + checkR[d]][j + checkC[d]]; } res += cnt >> 2; } } return res; } void makeDragon(int nD, int sede) { int nowLength = 1; for (int i = 0; i < sede; i++) { for (int j = nowLength - 1; j >= 0; j--) { int dir = inv[direct[nD][j]]; direct[nD][nowLength++] = dir; dragon[nD].r += dr[dir]; dragon[nD].c += dc[dir]; map[dragon[nD].r][dragon[nD].c] = 1; } } } void init() { cin >> n; memset(map, 0, sizeof(map)); for (int i = 0; i < n; i++) { cin >> dragon[i].c >> dragon[i].r >> direct[i][0] >> sede[i]; map[dragon[i].r][dragon[i].c] = 1; dragon[i].r += dr[direct[i][0]]; dragon[i].c += dc[direct[i][0]]; map[dragon[i].r][dragon[i].c] = 1; } } }DragonInfo; int main() { DragonInfo.init(); int res = DragonInfo.getSagack(); cout << res << '\n'; return 0; } | cs |
시간 복잡도
드래곤의 세대의 수가 많아질수록 시간복잡도가 커지기 떄문에
가장 세대가 많은 드래곤의 세대 수를 maxn이라고 했을때, 입니다.
'공부 > 알고리즘 문제풀이' 카테고리의 다른 글
[삼성 기출 문제] 백준 16234 인구 이동 (2) | 2019.03.12 |
---|---|
[삼성 기출 문제] 백준15686 치킨 배달 (0) | 2019.03.12 |
[삼성 기출 문제] 백준15684 사다리 조작 (0) | 2019.03.11 |
[삼성 기출 문제] 백준 15683 감시 (0) | 2019.03.11 |
[삼성 기출 문제] 백준 14891 톱니바퀴 (3) | 2019.03.09 |