문제 이해
알고리즘 구현
알고리즘
#include <string>
#include <vector>
using namespace std;
vector<int> answer;
int num;
int mapping(int y, int x) {
return ((y + 1) * y / 2 + x);
}
pair<int, int> fillDown(int y, int x, int turn) {
pair<int, int> yx = make_pair(y, x);
int dy = 0;
while (dy < turn) {
yx.first = y + dy;
answer[mapping(yx.first, yx.second)] = num++;
++dy;
}
return (yx);
}
pair<int, int> fillRight(int y, int x, int turn) {
pair<int, int> yx = make_pair(y, x);
int dx = 0;
while (dx < turn) {
yx.second = x + dx;
answer[mapping(yx.first, yx.second)] = num++;
++dx;
}
return (yx);
}
pair<int, int> fillCross(int y, int x, int turn) {
pair<int, int> yx = make_pair(y, x);
int dc = 0;
while (dc < turn) {
yx.first = y - dc;
yx.second = x - dc;
answer[mapping(yx.first, yx.second)] = num++;
++dc;
}
return (yx);
}
vector<int> solution(int n) {
int totNum = (n + 1) * n / 2;
answer.resize(totNum);
num = 1;
pair<int, int> yx = make_pair(-1, 0);
int turn = n;
while (1) {
yx = fillDown(yx.first + 1, yx.second, turn--);
if (turn == 0) break;
yx = fillRight(yx.first, yx.second + 1, turn--);
if (turn == 0) break;
yx = fillCross(yx.first - 1, yx.second - 1, turn--);
if (turn == 0) break;
}
return answer;
}