[백준] 17143번*
💻 C++ 기반
✔️ 상어의 속도가 최대 1,000이므로 한 칸씩 이동하는 건 시간초과
✔️ 상어가 제자리로 돌아오는 최대의 이동횟수를 제외하고 for문 돌리기 (제자리로 돌아오는 이동횟수로 나눈 나머지만큼 for문 돌리기)
#include <cstdio>
#include <unordered_map>
#define MAX 101
using namespace std;
int R, C, M;
pair<pair<int, int>, int> ground[MAX][MAX];
pair<pair<int, int>, int> ground_copy[MAX][MAX];
int dy[5] = {0, -1, 1, 0, 0};
int dx[5] = {0, 0, 0, 1, -1};
unordered_map<int, int> opposite_dir;
int main()
{
opposite_dir[1] = 2;
opposite_dir[2] = 1;
opposite_dir[3] = 4;
opposite_dir[4] = 3;
scanf("%d %d %d", &R, &C, &M);
for (int i = 0; i < M; i++)
{
int r, c, s, d, z;
scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
ground[r][c] = make_pair(make_pair(s, d), z);
}
int ans = 0;
for (int j = 1; j <= C; j++)
{
/* 2번 과정 */
for (int i = 1; i <= R; i++)
{
if (ground[i][j].second != 0)
{
// 상어가 존재
ans += ground[i][j].second;
ground[i][j] = make_pair(make_pair(0, 0), 0);
M--;
break;
}
}
/* 3번 과정 */
for (int row = 1; row <= R; row++)
{
for (int col = 1; col <= C; col++)
{
ground_copy[row][col] = make_pair(make_pair(0, 0), 0);
}
}
for (int row = 1; row <= R; row++)
{
for (int col = 1; col <= C; col++)
{
if (ground[row][col].second != 0)
{
int curY = row;
int curX = col;
int velocity = ground[row][col].first.first;
int dir = ground[row][col].first.second;
int size = ground[row][col].second;
int mod = dir == 1 || dir == 2 ? velocity % ((R - 1) * 2) : velocity % ((C - 1) * 2);
for (int move = 0; move < mod; move++)
{
int nextY = curY + dy[dir];
int nextX = curX + dx[dir];
if (nextY < 1 || nextY > R || nextX < 1 || nextX > C)
{
dir = opposite_dir[dir];
move--;
}
else
{
curY = nextY;
curX = nextX;
}
}
if (ground_copy[curY][curX].second < size)
{
ground_copy[curY][curX] = make_pair(make_pair(velocity, dir), size);
}
}
}
}
for (int row = 1; row <= R; row++)
{
for (int col = 1; col <= C; col++)
{
ground[row][col] = ground_copy[row][col];
}
}
}
printf("%d", ans);
return 0;
}
Author And Source
이 문제에 관하여([백준] 17143번*), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jieun_han/백준-17143번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)