문제를 잘못이해해서 상어가 이동중에 만나는 경우에도 서로 잡아먹는걸 고려해서 짠 코드.....미완성이지만 아까워서 기록용으로 올려놓습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
#include<iostream>
#include <string>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int R, C,M;
struct shark {
int y, x, spd, dir, size, chk;
};
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
vector<shark> v;
vector<shark> tmp;
//a상어와 b상어가 만나는지
bool meet(int a, int b) {
//서로 나눌수 있는 관계여야 만날가능성 있음.
int arr_b[101][101];
int arr_a[101][101];
//초기화
for (int i = 0; i < 101; i++)
for (int j = 0; j < 101; j++)
arr_a[i][j] = arr_b[i][j] = 0;
//서로 나눌수 있는 관계가 아니면 만날일 없음.
if (!(v[a].spd%v[b].spd == 0 || v[b].spd % v[a].spd == 0))
return false;
//현재 동일한 위치면 만남.
if (v[a].y == v[b].y && v[a].x == v[b].x)
return true;
int y = v[a].y; int x = v[a].x;
for (int i = 1; i <=v[a].spd; i++) {
int ny = y + dy[v[a].dir];
int nx = x + dx[v[a].dir];
if (1 > ny || ny > R || 1 > nx || nx > C) {
v[a].dir = (v[a].dir + 2) % 4;
ny = y + dy[v[a].dir];
nx = x + dx[v[a].dir];
}
arr_a[ny][nx] = i;
y = ny; x = nx;
}
y = v[b].y; x = v[b].x;
for (int i = 1; i <= v[b].spd; i++) {
int ny = y + dy[v[b].dir];
int nx = x + dx[v[b].dir];
if (1 > ny || ny > R || 1 > nx || nx > C) {
v[b].dir = (v[b].dir + 2) % 4;
ny = y + dy[v[b].dir];
nx = x + dx[v[b].dir];
}
arr_b[ny][nx] = i;
//시간초과 안나려면 여기서 체크해야됨.
//거리 넣을때마다 a이동하는 곳과 겹치는지 체크
//a거리*b속력 == b거리*a속력 인 경우 상어가 만남.
if (arr_a[ny][nx] != 0) {
if (arr_a[ny][nx] * v[b].spd == arr_b[ny][nx] * v[a].spd)
return true;
}
y = ny; x = nx;
}
return false;
}
int main(void) {
int ret = 0;
int y, x, spd, dir, size;
cin >> R >> C>>M;
v.resize(M);
tmp.resize(M);
for (int i = 0; i < M; i++) {
cin >> y >> x >> spd >> dir >> size;
v[i].y = y; v[i].x = x; v[i].spd = spd; v[i].dir = dir; v[i].size = size; v[i].chk = 1;
}
//pos는 낚시왕 위치
for (int pos = 1; pos <= C; pos++) {
int dist = 111; int pick = -1;
//상어 고르기
for (int spos = 0; spos < M; spos++) {
//먹혔거나 잡은 상어면 continue
if (v[spos].chk == 0)
continue;
//낚시왕과 같은 열에서 행의 거리가 짧은 상어 골라야됨.
if (v[spos].x == pos && v[spos].y < dist) {
dist = v[spos].y;
pick = spos;
}
}
//상어를 잡았다면
if (pick != -1) {
v[pick].chk = 0;
ret += v[pick].size;
}
for (int i = 0; i < M - 1; i++) {
for (int j = i + 1; j < M; j++) {
//만약 만난다면 사이즈큰 상어가 살아남음.
if (meet(i, j)) {
}
}
}
}
}
|
cs |
다음 코드는 시간초과 나는 코드 M이 최대값 1만이고 1만*1만 for문 2중루프라 괜찮을 줄 알았는데 시간초과나네요.
질문검색을 보니 상어를 하나하나 한칸씩 이동시키니 시간초과가 발생하는듯 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
#include<iostream>
#include <string>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int R, C,M;
struct shark {
int y, x, spd, dir, size, chk;
};
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
vector<shark> v;
int main(void) {
int ret = 0;
int y, x, spd, dir, size;
cin >> R >> C>>M;
v.resize(M);
for (int i = 0; i < M; i++) {
cin >> y >> x >> spd >> dir >> size;
if (dir == 1) {
dir = 3;
}
else if (dir == 2) {
dir = 1;
}
else if (dir == 3) {
dir = 0;
}
else if (dir == 4) {
dir = 2;
}
v[i].y = y; v[i].x = x; v[i].spd = spd; v[i].dir = dir; v[i].size = size; v[i].chk = 1;
}
//pos는 낚시왕 위치
for (int pos = 1; pos <= C; pos++) {
int dist = 111; int pick = -1;
//상어 고르기
for (int spos = 0; spos < M; spos++) {
//먹혔거나 잡은 상어면 continue
if (v[spos].chk == 0)
continue;
//낚시왕과 같은 열에서 행의 거리가 짧은 상어 골라야됨.
if (v[spos].x == pos && v[spos].y < dist) {
dist = v[spos].y;
pick = spos;
}
}
//상어를 잡았다면
if (pick != -1) {
//잡은상어 체크
v[pick].chk = 0;
//정답값에 크기만큼더하기
ret += v[pick].size;
}
int ny, nx, y, x;
//상어 이동
for (int k = 0; k < M; k++) {
y = v[k].y; x = v[k].x;
for (int i = 1; i <= v[k].spd; i++) {
ny = y + dy[v[k].dir];
nx = x + dx[v[k].dir];
//막다른길이면 반대방향으로 가기
if (1 > ny || ny > R || 1 > nx || nx > C) {
v[k].dir = (v[k].dir + 2) % 4;
ny = y + dy[v[k].dir];
nx = x + dx[v[k].dir];
}
y = ny; x = nx;
}
v[k].y = y; v[k].x = x;
}
for (int i = 0; i < M - 1; i++) {
if (v[i].chk == 0)
continue;
for (int j = i + 1; j < M; j++) {
if (v[j].chk == 0)
continue;
//이동후에 같은위치에있는 경우 크기가 큰상어가 작은상어잡아먹음.
if (v[i].y == v[j].y && v[i].x == v[j].x) {
if (v[i].size > v[j].size)
v[j].chk = 0;
else
v[i].chk = 0;
}
}
}
}
cout << ret;
return 0;
}
|
cs |
저녁에 다시풀어봐야겠다
'알고리즘 > BAEKJOON' 카테고리의 다른 글
| [c++] 1043번 거짓말 (유니온 파인드) (0) | 2022.09.27 |
|---|---|
| [c++] 백준 1976번 여행 가자 (유니온-파인드) (0) | 2022.09.27 |
| 백준 5014번 스타트 링크 시간초과 (0) | 2021.05.15 |
| 백준 17135번 캐슬 디펜스 (0) | 2021.05.12 |
| 백준 14502번 연구소 (0) | 2019.09.19 |