좌표 위의 점의 이동을 구현하는 문제이다. 각 세대마다 이전 세대는 시계 방향으로 90도 회전시킨 후 끝 점에 이어 붙인다. 점을 90도 회전하는 공식은 (xcosθ - ysinθ, xsinθ + ycosθ)
를 사용했다. 90도를 회전하므로 회전 후 좌표는 (-y, x)
가 된다. 먼저 0세대 좌표부터 v
에 넣어주고 남은 세대만큼 반복문을 돌아준다. 반복문을 돌며 회전 후의 좌표를 구해 v
에 넣어주고 이를 반복한다. 이때 회전의 기준은 항상 이전 세대의 마지막 좌표가 되므로 회전 전에 (0,0)
으로 옮기기 위해 빼주고 회전 후 다시 더해준다. 이 과정을 반복하며 좌표에 해당하는 위치를 A
에서 true
로 바꿔주고 4개의 꼭지점이 true
인 것을 찾아 카운트해주었다.
생각보다 간단하게 풀 수 있었던 문제였다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int x, y, d, g;
bool A[101][101];
int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };
void solution() {
vector<pair<int, int>> v;
int ny = y + dy[d];
int nx = x + dx[d];
v.push_back({ y,x });
v.push_back({ ny,nx });
A[y][x] = true;
A[ny][nx] = true;
for (int i = 0; i < g; i++) {
int size = v.size();
int cy = v.back().first;
int cx = v.back().second;
for (int j = size - 2; j >= 0; j--) {
int ty = v[j].first - cy;
int tx = v[j].second - cx;
int gy = tx + cy;
int gx = -ty + cx;
v.push_back({ gy,gx });
A[gy][gx] = true;
}
}
}
void result() {
int answer = 0;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if (A[i][j] && A[i + 1][j] && A[i][j + 1] && A[i + 1][j + 1]) {
answer++;
}
}
}
cout << answer;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N;
cin >> N;
while (N--) {
cin >> x >> y >> d >> g;
solution();
}
result();
return 0;
}