17143번: 낚시왕
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.
www.acmicpc.net
1. 풀이방법
- 비교적 간단한 구현 문제입니다.
- 1단계가 낚시왕의 이동, 2단계가 낚시, 3단계가 상어의 이동입니다.
- 1,2 단계는 매우 쉽고, 3단계에서 최대 상어의 마리수 M =10000이고, 한번에 이동할 수 있는 칸은 최대 1000칸 이므로
- 한칸씩 상어를 이동시킬 경우 10000000 에, 다른 부가적인 작업들이 들어가면 시간초과 가능성이 있다고 판단하여
- 문제의 사진을 잘 분석해 보면 한칸씩 이동시키는 것이 어떤 수가 되었을 때 정확히 같은방향, 같은 자리로 오는지를
- 파악해보면, ( 2 * ((R or C)-1) ) 칸을 움직이면 같은방향을 가지면서 같은 자리로 이동합니다.
- 즉 최종으로 한칸씩 이동시킬 fixedmovecount= speed % ( 2 * ((R or C)-1) ) 만큼만 한칸 씩 이동시키면 됩니다.
2. 주의사항
- 모듈러연산을 활용한다 정도?
- 문제도 짧고 헷갈릴만한 단어도 딱히 없었습니다...
3. 나의코드
#include<bits/stdc++.h>
using namespace std;
int R, C,M;
struct shark {
int speed, dir, ssize,num;
};
vector<shark> sea[102][102];
vector<pair<int, int>> sharkvec; // 상어들의 위치 저장
bool sharkdie[10001]; // 상어 살았는지 여부 조사
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };
int sharksum;
void inputs() {
cin >> R >> C>>M;
int r, c, s, d, z;
for (int i = 0; i < M; i++) {
cin >> r >> c >> s >> d >> z;
sharkvec.push_back({ r,c });
sea[r][c].push_back({ s,d - 1,z,i });
}
}
void getshark(int f) {
for (int i = 1; i <= R; i++) {
if (!sea[i][f].empty()) {
sharksum += sea[i][f][0].ssize; //잡음
sharkdie[sea[i][f][0].num] = true;
sea[i][f].pop_back();
return;
}
}
return;
}
void moveshark() {
vector<shark> tmpsea[102][102];
for (int i = 0; i < M; i++) {
if (sharkdie[i]) continue; //죽었으면 보지않음
int x = sharkvec[i].first; int y = sharkvec[i].second;
int tmps, tmpd, tmpz;
tmps = sea[x][y][0].speed;
tmpz = sea[x][y][0].ssize; //크기
tmpd = sea[x][y][0].dir;
int fixexmovecount;
if (tmpd <= 1) { // 세로이동
fixexmovecount = tmps%(2*(R - 1));
for (int a = 0; a < fixexmovecount; a++) {
if (x == R) { tmpd = 0; }
if (x == 1) { tmpd = 1; }
x += dx[tmpd];
}
}
else { //가로이동
fixexmovecount = tmps%(2*(C - 1));
for (int a = 0; a < fixexmovecount; a++) {
if (y == C) { tmpd = 3; }
if (y == 1) { tmpd = 2; }
y += dy[tmpd];
}
}
sharkvec[i].first = x; sharkvec[i].second = y;
if(tmpsea[x][y].empty()) tmpsea[x][y].push_back({ tmps,tmpd,tmpz,i }); //아무도 없으면 그냥 삽입
else { //다른 상어가 있으면 큰놈이 작은놈을 잡아먹는다
if (tmpsea[x][y][0].ssize < tmpz) {
sharkdie[tmpsea[x][y][0].num] = true; // 기존에 있던놈 잡아먹힘
tmpsea[x][y].pop_back();
tmpsea[x][y].push_back({ tmps,tmpd,tmpz,i });
}
else { //넣으려던놈이 잡아먹힘
sharkdie[i] = true;
}
}
}
for (int t = 1; t <= R; t++) {
for (int k = 1; k <= C; k++) {
sea[t][k] = tmpsea[t][k];
}
}
return;
}
/*void watchshark() {
cout << "\n";
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
if (sea[i][j].empty()) cout << 0 << " ";
else cout << sea[i][j][0].num+1 << " ";
}
cout << "\n";
}
cout << "\n";
}*/
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inputs();
for (int fm = 1; fm <= C; fm++) { // 낚시꾼의 위치 (1초당)
getshark(fm);
moveshark();
}
cout << sharksum;
return 0;
}'알고리즘 문제풀이 > 구현' 카테고리의 다른 글
| 백준 17822 [C++] (0) | 2021.03.08 |
|---|---|
| 백준 17825 [C++] (0) | 2021.03.07 |
| 백준 17837 [C++] (0) | 2021.03.06 |
| 백준 16235 [C++] (0) | 2021.03.06 |
| 백준 17779 [C++] (0) | 2021.03.05 |
