[12] 드래곤 커브(15685) C++

 

 

 

 

 

 

 

 

• 15685번

15685번 - 드래곤 커브 성공

 

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

출력

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

제한

 

예제 입력 1

3
3 3 0 1
4 2 1 3
4 2 2 1

예제 출력 1

4

예제 입력 2

4
3 3 0 1
4 2 1 3
4 2 2 1
2 7 3 4

예제 출력 2

11

예제 입력 3

10
5 5 0 0
5 6 0 0
5 7 0 0
5 8 0 0
5 9 0 0
6 5 0 0
6 6 0 0
6 7 0 0
6 8 0 0
6 9 0 0

예제 출력 3

8

예제 입력 4

4
50 50 0 10
50 50 1 10
50 50 2 10
50 50 3 10

예제 출력 4

1992

힌트

예제 1	예제 2

출처

• 문제를 만든 사람: baekjoon
• 문제의 오타를 찾은 사람: jh05013

알고리즘 분류

• 시뮬레이션

메모

 

메모 작성하기

 

 

 

 

 

===========================================================================

시뮬레이션 문제로서, 규칙을 찾아서 문제에 나와있는대로 구현하면 된다.

여기서 중요했던 로직은 미리 이동할 방향에 대한 배열을 저장해두어 시작점에서 해당 direction 방향으로 이동하면서 점을 찍는 것이 중요하다. 

그런데 이동할 방향에 대한 배열을 90도 회전 후 적용되는 것이므로 

0 → 1

1 → 2

2 → 3

3 → 0                   ==> 순서로   이동하게 되는데, 여기서 중요한 것은 바꿔준 다음 거꾸로 집어넣어야 한다. 

그 이유는 시작점에서 연결하는게 아니라 끝점에서 해당 복사된 방향으로 이동해야하기 때문에 뒤에서부터 1로 순서를 집어넣어야 한다. 

 

코드는 다음과 같다. 

 

 

#include<iostream> using namespace std; int test[30][6], temp[99999]; int arr[2000][2000]; int order[30][99999]; int N, now, cnt = 0, answer = 0; void start(int idx); void print(int idx); void makeOrder(int idx, int generation); pair<int, int> p[99999]; int main(void) { int x, y, d, g; cin >> N; for (int i = 1; i <= N; i++){ cin >> x >> y >> d >> g; test[i][1] = x+1000; test[i][2] = y+1000; test[i][3] = d; test[i][4] = g; test[i][5] = 1; } for (int i = 1; i <= N; i++) start(i); for (int i = 1; i <= cnt; i++) { int tempx = p[i].first; int tempy = p[i].second; if (arr[tempx][tempy] == 1){ if (arr[tempx][tempy + 1] == 1){ if (arr[tempx + 1][tempy] == 1){ if (arr[tempx + 1][tempy + 1] == 1){ answer++; } } } } } cout <<answer<< endl; return 0; } void start(int idx) { int dx = test[idx][1]; int dy = test[idx][2]; if (arr[dx][dy] == 0) { cnt++; p[cnt].first = dx; p[cnt].second = dy; arr[dx][dy] = 1; } now = test[idx][5]; order[idx][now] = test[idx][3]; for (int i = 1; i <= test[idx][4]; i++) makeOrder(idx,i); for (int i = 1; i <= now; i++) { if (order[idx][i] == 0){//right dx += 1; if (arr[dx][dy] == 0) { cnt++; p[cnt].first = dx; p[cnt].second = dy; arr[dx][dy] = 1; } } else if (order[idx][i] == 1){//up dy -= 1; if (arr[dx][dy] == 0) { cnt++; p[cnt].first = dx; p[cnt].second = dy; arr[dx][dy] = 1; } } else if (order[idx][i] == 2){//left dx -= 1; if (arr[dx][dy] == 0) { cnt++; p[cnt].first = dx; p[cnt].second = dy; arr[dx][dy] = 1; } } else{//down dy += 1; if (arr[dx][dy] == 0) { cnt++; p[cnt].first = dx; p[cnt].second = dy; arr[dx][dy] = 1; } } } } void makeOrder(int idx,int generation) { for (int i = now; i >= 1; i--) { if (order[idx][i] == 0) temp[now-i+1] = 1; if (order[idx][i] == 1) temp[now - i + 1] = 2; if (order[idx][i] == 2) temp[now - i + 1] = 3; if (order[idx][i] == 3) temp[now - i + 1] = 0; } for (int i = now + 1; i <= now + now; i++) order[idx][i] = temp[i - now]; now = 2 * now; //print(idx); } void print(int idx) { for (int i = 1; i <= now; i++) cout << order[idx][i] << ' '; cout << "now is " << now << endl; cout << endl; }

반응형

저작자표시 비영리 변경금지

'알고리즘( C++ ) > 1. BOJ' 카테고리의 다른 글

[14] 2048(Easy)(12100) C++  (0)	2019.04.08
[13] 연구소(14502) C++  (0)	2019.04.07
[11] 구슬 탈출2(13460) C++  (0)	2019.04.02
[10] 배열 돌리기1(16926) C++  (0)	2019.04.01
[9] 인구 이동(16234) C++  (0)	2019.03.31

'알고리즘( C++ )/1. BOJ' Related Articles

• [14] 2048(Easy)(12100) C++ 2019.04.08
• [13] 연구소(14502) C++ 2019.04.07
• [11] 구슬 탈출2(13460) C++ 2019.04.02
• [10] 배열 돌리기1(16926) C++ 2019.04.01

more

Comments