0: x좌표가 증가하는 방향 (→)
1: y좌표가 감소하는 방향 (↑)
2: x좌표가 감소하는 방향 (←)
3: y좌표가 증가하는 방향 (↓)
0세대: 0
1세대: 01
2세대: 0121
3세대: 01212321
......
과 같이 나타낼 수 있다.
규칙을 찾아보자면 n세대
는 n-1세대 + n-1세대 길이만큼의 무언가
이다
여기서 n-1세대 길이만큼의 무언가
는 잘 보면 규칙을 찾을 수 있다.
n-1세대
를 거꾸 나타낸 것에서 각 자리에 +1
이다. 정확히 말하면 (+1)%4
이다
위에서 2세대는 0121
이다. 그렇다면 3세대는 0121
+ 2세대를 거꾸로 한 것 (+1%)4
즉 0121
을 거꾸로한 1210
에 각 자리수에 1을 더해주고 4를 나눠준 값을 0121
뒤에 쓴다. 따라서 0121 2321
이 된다
👩💻1. make Curve
- 먼저
dir_info
에는 각 세대마다 방향에 관한 정보를 포함한다.makeCurve()
함수 에서는 현재dir_info
에 저장되어 있는 세대의 다음 세대를 만들어 준다. 즉,dir_info
에2세대
방향 정보{0121}
가 들어있다면{2321}
을 추가로 덧붙여{01212321}
을 만들어주는 함수다void makeCurve() { int s = dir_info.size(); for (int i = s - 1; i >= 0; i--) { int nd = (dir_info[i] + 1) % 4; y = y + dy[nd]; x = x + dx[nd]; map[y][x] = 1; dir_info.push_back(nd); } }
- 드래곤 커브의 끝점마다
1
로 표시해주어 드래곤 커브가 지나간 자리라는 것을 표시해준다
makeCurve()
를 호출할 때는 먼저
ⓐ입력받은(y,x)
좌표에 점을 찍어주고map[y][x]=1
,
ⓑ(y,x)
에서 입력받은 방향d
로 한 칸 이동한 좌표를 다시(y,x)
로 만들어주고
ⓒ해당 지점에map[y][x]=1
를 해준다.
ⓓ이렇게 처음 입력받은y,x,d
좌표에 의해0세대
가 만들어진다.
ⓔ그 후g
에 따라g
만큼 반복해서makeCurve()
함수를 호출한다.for (int i = 0; i < N; i++) { cin >> x >> y >> d >> g; dir_info.clear(); map[y][x] = 1; //ⓐ y = y + dy[d]; //ⓑ x = x + dx[d]; //ⓑ map[y][x] = 1; //ⓒ dir_info.push_back(d); //ⓓ for (int j = 0; j < g; j++) //ⓔ makeCurve(); }
👩💻2. count()
- 네 꼭지점이 모두 드래곤 커브에 일부인 것의 개수를 출력해야 하므로 사각형 모양으로 인접한 네 지점이 모두
map
상에서1
인 것을 찾는다void count() { for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) { if (map[i][j] == 1 && map[i + 1][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j + 1] == 1) cnt++; } } }
전체코드
#include <iostream> #include <vector> using namespace std; const int MAX = 101; int dy[] = { 0,-1,0,1 }; int dx[] = { 1,0,-1,0 }; vector<int> dir_info; int map[MAX][MAX]; int N, x, y, d, g; int cnt; void count() { for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) { if (map[i][j] == 1 && map[i + 1][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j + 1] == 1) cnt++; } } } void makeCurve() { int s = dir_info.size(); for (int i = s - 1; i >= 0; i--) { int nd = (dir_info[i] + 1) % 4; y = y + dy[nd]; x = x + dx[nd]; map[y][x] = 1; dir_info.push_back(nd); } } void solution() { cin >> N; for (int i = 0; i < N; i++) { cin >> x >> y >> d >> g; dir_info.clear(); map[y][x] = 1; y = y + dy[d]; x = x + dx[d]; map[y][x] = 1; dir_info.push_back(d); for (int j = 0; j < g; j++) makeCurve(); } count(); } int main() { solution(); cout << cnt << endl; return 0; }