Problem 문제풀이
구현을 실수없이 하는 능력을 필요로 하는 문제였다.
전략
-
낚시왕의 idx를 증가시키고 상어를 잡는다.
-
상어를 이동시킨다.
-
낚시왕이 가장 오른쪽 칸에 이동하면 잡은 상어의 크기의 합을 출력한다.
너무나도 직관적인 문제이기에 구현만 잘하면 된다. 먼저 상어의 정보를
저장할 struct를 만들어보자. 무려 5개나 된다.
struct Shark {
int row;
int col;
int speed;
int dir;
int size;
Shark(int _row, int _col, int _speed, int _dir, int _size) :row(_row - 1), col(_col - 1), speed(_speed), dir(_dir - 1), size(_size) {}
};
지금 생각하는 거지만 상어의 정보에 bool is_dead 같은 것을 넣었으면 좋았을 것 같다.
이제 simulation을 구현해보자.
void simulation()
{
for (int idx = 0; idx < C; idx++)
{
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
board[(idx + 1) % 2][i][j] = -1;
}
}
for (int i = 0; i < R; i++)
{
int target = board[idx % 2][i][idx];
if (target != -1)
{
answer += shark[target].size;
shark[target].row = -1;
shark[target].col = -1;
break;
}
}
move(idx);
}
cout << answer;
}
정말 간단하지 않은가? move함수만 잘 만들면 나머지는 할 게 없는 문제이다.
그러나 move함수를 만들 때 조금 생각을 해야한다.
void move(int idx)
{
for (int i = 0; i < shark.size(); i++)
{
if (shark[i].row == -1 && shark[i].col == -1)
{
continue;
}
상어가 죽거나 낚시왕에게 잡혔을 경우 row와 col을 -1로 바꿔주었다.
erase할지 이렇게 할지 고민하다 index를 더 활용하기 위해 이런 방식을 택했다.
int nR = shark[i].row + shark[i].speed * dirR[shark[i].dir];
int nC = shark[i].col + shark[i].speed * dirC[shark[i].dir];
while (nR < 0 || nR >= R || nC < 0 || nC >= C)
{
if (nR < 0)
{
nR *= -1;
shark[i].dir = 1; // 아래
}
else if (nR >= R)
{
nR = 2 * R - nR - 2; //R-1-(nR-(R-1))
shark[i].dir = 0; //위
}
else if (nC < 0)
{
nC *= -1;
shark[i].dir = 2; //오른쪽
}
else if (nC >= C)
{
nC = 2 * C - nC - 2; //C-1-(nC-(C-1))
shark[i].dir = 3; //왼쪽
}
}
shark[i].row = nR;
shark[i].col = nC;
좌표 이동에서 한 번 실수를 하였다. boundary를 넘어갈 경우 그 거리만큼
반대로 보내면 끝이라 생각했는데 속도가 너무 빨라서 boundary를 여러 번
넘어갈 수 있다는 것을 간과하였다. shark의 속도를 무시하지 말자.
int next = board[(idx + 1) % 2][nR][nC];
if (next == -1)
{
board[(idx + 1) % 2][nR][nC] = i;
}
else
{
if (shark[next].size < shark[i].size)
{
board[(idx + 1) % 2][nR][nC] = i;
shark[next].row = -1;
shark[next].col = -1;
}
else
{
shark[i].row = -1;
shark[i].col = -1;
}
}
마지막으로 지금 내가 이동할 칸에 먼저 온 상어가 있다면 둘 중 하나를 죽여야한다
꼭 그렇게 죽여야만 속이 후련읍읍…
size가 작은 놈을 살포시 제거하자.
1제출 1맞았습니다 횟수가 늘고 있어서 기분이 좋다. 방심하지 말고 끝까지 확인하는 습관을 갖자.
전체 코드를 남기며 마무리한다.
#include <iostream>
#include <vector>
using namespace std;
struct Shark {
int row;
int col;
int speed;
int dir;
int size;
Shark(int _row, int _col, int _speed, int _dir, int _size) :row(_row - 1), col(_col - 1), speed(_speed), dir(_dir - 1), size(_size) {}
};
int R, C, M;
int r, c, s, d, z, answer;
int dirR[4] = { -1,1,0,0 };
int dirC[4] = { 0,0,1,-1 };
int board[2][101][101];
vector<Shark>shark;
void move(int idx);
void simulation();
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> R >> C >> M;
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
board[0][i][j] = -1;
}
}
for (int i = 0; i < M; i++)
{
cin >> r >> c >> s >> d >> z;
shark.push_back(Shark(r, c, s, d, z));
board[0][r - 1][c - 1] = i;
}
simulation();
return 0;
}
void move(int idx)
{
for (int i = 0; i < shark.size(); i++)
{
if (shark[i].row == -1 && shark[i].col == -1)
{
continue;
}
int nR = shark[i].row + shark[i].speed * dirR[shark[i].dir];
int nC = shark[i].col + shark[i].speed * dirC[shark[i].dir];
while (nR < 0 || nR >= R || nC < 0 || nC >= C)
{
if (nR < 0)
{
nR *= -1;
shark[i].dir = 1; // 아래
}
else if (nR >= R)
{
nR = 2 * R - nR - 2; //R-1-(nR-(R-1))
shark[i].dir = 0; //위
}
else if (nC < 0)
{
nC *= -1;
shark[i].dir = 2; //오른쪽
}
else if (nC >= C)
{
nC = 2 * C - nC - 2; //C-1-(nC-(C-1))
shark[i].dir = 3; //왼쪽
}
}
shark[i].row = nR;
shark[i].col = nC;
int next = board[(idx + 1) % 2][nR][nC];
if (next == -1)
{
board[(idx + 1) % 2][nR][nC] = i;
}
else
{
if (shark[next].size < shark[i].size)
{
board[(idx + 1) % 2][nR][nC] = i;
shark[next].row = -1;
shark[next].col = -1;
}
else
{
shark[i].row = -1;
shark[i].col = -1;
}
}
}
}
void simulation()
{
for (int idx = 0; idx < C; idx++)
{
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
board[(idx + 1) % 2][i][j] = -1;
}
}
for (int i = 0; i < R; i++)
{
int target = board[idx % 2][i][idx];
if (target != -1)
{
answer += shark[target].size;
shark[target].row = -1;
shark[target].col = -1;
break;
}
}
move(idx);
}
cout << answer;
}