반응형

https://www.acmicpc.net/problem/17143

 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.

www.acmicpc.net

 

[ 문제풀이 ]

 

처음에 풀이 방법을 떠올리기까지 30분 정도 걸린 것 같습니다.

 

먼저 상어의 속도와 관련해서 일정 속도 이상이면 제자리에 여러 번 도착한다는 것을 알았습니다. 그렇다면 제자리로 오기까지의 속도는 시뮬레이션 결과에 큰 영향을 미치지 않는다고 생각을 했고, 제자리에 오는 데 걸리는 시간으로 속도를 나누어 주었습니다. 그리고 속도를 그 나머지 값으로 경신해주었습니다.

위의 그림을 보면 총 이동거리 10일 때 제자리로 돌아온다는 것을 알 수 있습니다. 바로 총 거리 - 1을 두 배 해준 값이 됩니다. 따라서 모든 상어의 속도 s를 (총 거리 - 1) * 2로 나눈 나머지 값으로 경신시켜줍니다. 그렇게 되면 시뮬레이션 시간도 대폭 감소될 것이고 시간제한도 피할 수 있을 것입니다.

 

이후 시뮬레이션을 통해 상어들을 이동시켜 주었고, visited배열을 통해서 미리 도착해 있던 상어가 있다면 크기 비교 후 더 작다면 없애고, 더 크다면 방금 도착한 상어를 없애주는 방법으로 구현하였습니다.

 

 

[ 소스 코드 ]

 

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
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <cstring>
 
using namespace std;
 
struct shark {
    int r;
    int c;
    int s;
    int d;
    int z;
};
 
int R, C, M;
shark arr[10001];                    //각 상어의 정보를 저장발 배열
int dr[5] = { 0,-1,1,0,0 };            //방향 배열
int dc[5] = { 0,0,0,1,-1 };
int visited[101][101];                //상어가 도착한 장소에 상어가 있는지 체크하기 위한 배열
 
int main()
{
    cin >> R >> C >> M;
    int idx = 1;
    int sum = 0;
 
    for (int i = 1; i <= M; i++) {
        int r, c, s, d, z;
        scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
        if (d < 3) {                //일정 속도 이상이면 여러번 제자리로 돌아오기 때문에
            s %= 2 * (R - 1);        //총 (길이-1)*2로 나눈 나머지 값을 속도에 넣어준다.
        }
        else {
            s %= 2 * (C - 1);
        }
        arr[i] = { r,c,s,d,z };
    }
 
    while (idx <= C)
    {
        memset(visited, 0, sizeof(visited));
        int min = 999;
        int x = 987654321;
        for (int i = 1; i <= M; i++) {        //현재 사람과 같은 위치에 있는 상어 중
            if (arr[i].r == 0) continue;    //가장 땅에 가까운 상어의 번호를 x에 저장
            if (idx == arr[i].c) {
                if (min > arr[i].r) {
                    min = arr[i].r;
                    x = i;
                }
            }
        }
        if (x != 987654321) {                //x가 경신 되었다면 그 상어를 없애고
            sum += arr[x].z;                //sum에 크기를 더해준다.
            arr[x] = { 0 };
        }
 
        for (int i = 1; i <= M; i++) {        //모든 상어를 움직인다.
            if (arr[i].r == 0) continue;
            int rr = arr[i].r;
            int cc = arr[i].c;
            for (int j = 0; j < arr[i].s; j++) {
                rr += dr[arr[i].d];
                cc += dc[arr[i].d];
                if (arr[i].d == 1) {
                    if (rr == 1) {
                        arr[i].d = 2;
                    }
                    else if (rr < 1) {
                        arr[i].d = 2;
                        rr = 2;
                    }
                }
                else if (arr[i].d == 2) {
                    if (rr == R) {
                        arr[i].d = 1;
                    }
                    else if (rr > R) {
                        rr = R - 1;
                        arr[i].d = 1;
                    }
                }
                else if (arr[i].d == 3) {
                    if (cc == C) {
                        arr[i].d = 4;
                    }
                    else if (cc > C) {
                        cc = C - 1;
                        arr[i].d = 4;
                    }
                }
                else if (arr[i].d == 4) {
                    if (cc == 1) {
                        arr[i].d = 3;
                    }
                    else if (cc < 1) {
                        arr[i].d = 3;
                        cc = 2;
                    }
                }
            }
            if (visited[rr][cc] == 0) {        //만약 처음 상어가 도착했다면
                visited[rr][cc] = i;        //visited배열에 상어 번호를 저장
                arr[i].r = rr;
                arr[i].c = cc;
            }
            else {                            //이미 와 있던 상어가 있다면
                if (arr[i].z > arr[visited[rr][cc]].z) {
                    arr[visited[rr][cc]] = { 0 };
                    visited[rr][cc] = i;    //크기를 비교 후 더 크면
                    arr[i].r = rr;            //visited배열을 경신해준다
                    arr[i].c = cc;
                }
                else {
                    arr[i] = { 0 };            //더 작다면 더 작은 상어를 없앤다.
                }
            }
        }
        idx++;                //오른쪽으로 옮긴다.
    }
 
    cout << sum;        //결과 출력
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
[ 백준 ] 16946번 - 벽 부수고 이동하기 4 (C++)  (0) 2022.05.22
[ 백준 ] 12100번 - 2048(Easy) (C++)  (0) 2022.05.21

+ Recent posts

티스토리툴바