취업 대비 알고리즘 포스팅에 SW 역량테스트는 별로 없고 카카오로만 그득해졌네요. 그래서 삼성 SW 역량 테스트 문제도 확인을 해보기 위해 검색을 해봤습니다. 시중에 SW역량테스트를 위해 공부해야하는 것들을 책으로도 팔고 있고, 많은 분들이 시험을 본 후 복원 리뷰와, 제가 대학교 시절 공부할 때 많이 도움됐던 백준 온라인 저지에도 복원문제가 많은 것이 보였습니다.
대학생 때부터 많이 모자라고 날고 긴다는 사람들에 비하면 거의 쩌리 수준에 한참 공부가 필요했던 저였지만, 그래도 대학생 때는 나름 꾸준히 문제를 풀기라도 했었는데.. 회사를 들어오고 실무를 시작하니 귀차니즘이 너무 강해져 버린 것 같습니다. 못하지만 소위 말하는 블루라도 계속 달아보려고 자주 참여하던 코드포스도 참여를 못하고, 그나마 겁없이 감도 안살리고 도전했다가 점수만 계속 깎아먹고 등급만 강등 당하고 복구도 못하고 있네요..
이런 저에게 여러모로 반성을 하게 됐습니다. 이제부터라도 포스팅을 핑계로 문제를 풀어보도록 해야 할 것 같습니다. 최대한 자주자주 ㅠㅠ 하겠습니다.
이제 포스팅을 시작하겠습니다. 먼저 이 문제는 백준 온라인 저지에 복원된 제목을 그대로 사용했으며, 검색을 해보니 2018년 상반기 평가로 추정됩니다. 이전 포스팅에서도 다뤘듯이, 삼성 SW 역량테스트는 A형에 해당하며 STL을 사용할 수 있고(사실 사용 안해도 풀 수 있는 문제들입니다), 3시간의 제한시간을 두고 있습니다.
문제는 드래곤 커브라는 개념을 다루고 있습니다. 드래곤 커브는 임의의 X세대에 대해, X+1세대는 X세대의 객체가 시계방향으로 90도 회전하여 마지막에 도달했던 점에 연결된다는 특성이 있습니다. 이렇게 주어진 모든 세대의 드래곤커브를 구현했을 때, 꼭지점이 모두 드래곤 커브가 그려진 1x1 의 정사각형 개수를 구하면 됩니다.
여기서 시계방향으로 90도 회전한다는 것이 문제 풀이의 핵심입니다. 시계방향으로 계속 회전하기 때문에, 이동 순서를 특정 배열에 정의해놓고 다음 세대에서는 +1을 하는 방식으로 규칙을 적용하여 드래곤 커브를 그릴 수 있게 됩니다. 저 같은 경우는 아래 소스와 같이 이동 순서를 배열로 정의해놓고, 각 index를 vector에 저장하게 하였습니다.
int dir[4][2] = { {1,0},{0,-1},{-1,0},{0,1} }, map[101][101];
그 다음, X+1 세대를 그릴 때는 X 세대의 마지막 index부터, 0번 index까지 for문을 돌아 저장된 index를 +1 하여 다음 방향의 index를 vector에 push 하였습니다. 이 때, 4로 나누어 주면서 index를 넣어주어야 원형으로 적용이 됩니다.
for (int i = 0; i < g; i++) {
int s = log.size() - 1;
for (int j = s; j >= 0; j--) {
int nd = (log[j] + 1) % 4;
log.push_back(nd);
//이하 생략
}
}
이렇게 하면 1세대에서는 1개, 2세대에서는 2개, 3세대에서는 4개, ... 가 필요하고 10세대에는 총 1024개의 정보가 저장됩니다. for문을 모두 돌릴 경우 $2^11-1$ 번 반복됩니다. 이렇게 직접 반복을 하면서 도달하는 점에 dragon curve가 지나갔다는 표시를 해주면 됩니다. 크기가 작기 때문에 직접 시뮬레이션을 할 수 있습니다.
그 다음 x,y(x>0, y>0) 좌표에 대해 (x-1,y-1) (x-1,y) (x,y-1) (x,y) 좌표가 모두 채워져 있는지 체크하여 정사각형의 개수를 세면 됩니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = { {1,0},{0,-1},{-1,0},{0,1} }, map[101][101];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x, y, d, g;
vector<int> log;
cin >> x >> y >> d >> g;
map[x][y] = 1;
x += dir[d][0], y += dir[d][1];
map[x][y] = 1;
log.push_back(d);
for (int i = 0; i < g; i++) {
int s = log.size() - 1;
for (int j = s; j >= 0; j--) {
int nd = (log[j] + 1) % 4;
log.push_back(nd);
x += dir[nd][0], y += dir[nd][1];
if (x >= 0 && x <= 100 && y >= 0 && y <= 100) {
map[x][y] = 1;
}
}
}
}
int ans = 0;
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 100; j++) {
if (map[i][j] && map[i - 1][j] && map[i][j - 1] && map[i - 1][j - 1])
ans++;
}
}
cout << ans;
}