[BOJ] 17143 : 낚시왕
풀이
2019 삼성전자 DS 상반기 오전 기출문제2번 변형문제.
시뮬레이션
시험장에서 짠거 보다 효율적으로 다시 짜보려고했는데, 똑같이 짜버렸다.
시험문제에서는 물고기idx가 순서대로 주어진것 같은데,
백준복원문제에서는 z값으로 입력받는다는 차이가 있다.
그리고 상어마리수도 원래 1000마리까지였는데 10000마리로 늘었다.
가로로 쭉 반복하면서 1.상어사냥하고, 2.arr초기화해주고, 3.상어이동시키고 4.상어arr에 배치
이순서대로 진행하면 된다.
move함수 같은 경우 s가 최대 1000이라 1칸씩 움직이도록 했더니 시험장에서는 시간초과가 났다.
그래서 가로-세로 x2(왕복) 길이로 mod연산을 사용해서 s의 복잡도를 줄였다.
백준에서도 시험장이랑 똑같이 (지저분하게) 구현해봤다.
이부분 효율적으로 바꿀수 있는 방법을 알고싶다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <queue>
using namespace std;
typedef struct Shark {
int x;
int y;
//스피드
int s;
//방향
int dir;
//살아있냐
int life;
}Shark;
int arr[100][100];
vector<Shark> sharks(10001);
const int dx[] = {-1,1,0,0};
const int dy[] = { 0,0,1,-1 };
int r, c, m;
void move(int idx) {
int x = sharks[idx].x;
int y = sharks[idx].y;
int s = sharks[idx].s;
int dir = sharks[idx].dir;
//남은값이 있음을 나타내는 flag
int flag = 0;
if (s == 0)
return;
//위
if (dir == 0) {
int num = x - s;
if (num < 0) {
dir = 1;
s -= x;
x = 0;
s = s%((r-1)*2);
flag = 1;
}
else if (num == 0) {
x = 0;
dir = 1;
}
else {
x = x - s;
}
}
//아래
else if (dir == 1) {
int num = r-1-x - s;
if (num < 0) {
s -= r - 1 - x;
x = r-1;
dir = 0;
s = s % ((r - 1) * 2);
flag = 1;
}
else if (num == 0) {
x = r-1;
dir = 0;
}
else {
x = x+s;
}
}
//오
else if (dir == 2) {
int num = c - 1 - y - s;
if (num < 0) {
s -= c - 1 - y;
y = c - 1;
dir = 3;
s = s % ((c - 1) * 2);
flag = 1;
}
else if (num == 0) {
y = c-1;
dir = 3;
}
else {
y = y + s;
}
}
//왼
else if (dir == 3) {
int num = y - s;
if (num < 0) {
s -= y;
y = 0;
dir = 2;
s = s % ((c - 1) * 2);
flag = 1;
}
else if (num == 0) {
y = 0;
dir = 2;
}
else {
y = y - s;
}
}
if (flag) {
while (s--) {
x = x + dx[dir];
y = y + dy[dir];
if (dir == 0 && x == 0)
dir = 1;
else if (dir == 1 && x == r - 1)
dir = 0;
else if (dir == 2 && y == c - 1)
dir = 3;
else if (dir == 3 && y == 0)
dir = 2;
}
}
sharks[idx].x = x;
sharks[idx].y = y;
sharks[idx].dir = dir;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 0; i <= 10000; i++) {
sharks[i] = { 0,0,0,0,0 };
}
//낚시왕
cin >> r >> c >> m;
for (int i = 0; i < m; i++) {
int x, y, s, dir, z;
cin >> x >> y >> s >> dir >> z;
dir--;
x--;
y--;
sharks[z] = {x,y,s,dir,1};
arr[x][y] = z;
}
int ans = 0;
for (int i = 0; i < c; i++) {
//상어사냥
for (int j = 0; j < r; j++) {
if (arr[j][i]>0) {
ans += arr[j][i];
sharks[arr[j][i]].life = 0;
break;
}
}
//초기화
memset(arr, 0, sizeof(arr));
//상어이동
for (int i = 1; i <= 10000; i++) {
if (sharks[i].life == 1) {
move(i);
}
}
//상어배치
for (int i = 1; i <= 10000; i++) {
if (sharks[i].life == 1) {
int x = sharks[i].x;
int y = sharks[i].y;
if (arr[x][y]>0) {
sharks[arr[x][y]].life = 0;
arr[x][y] = i;
}
else {
arr[x][y] = i;
}
}
}
/*
cout << '\n';
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << arr[i][j]<<' ';
}
cout << '\n';
}
*/
}
cout << ans;
return 0;
}
Written on April 20, 2019