일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 백준 1로 만들기
- 42서울 라피신 후기
- 백준 트리
- 백준 #백준4963 #섬의 개수
- ACM Craft
- 백준 9095
- 라피신 후기
- 백준 로프
- 백준 2217
- 백준 1003
- 백준 1068
- 백준 낚시왕
- BOGGLE
- 백준 1348
- 백준 경비행기
- 백준 9202
- 백준 주차장
- 42서울 후기
- 백준 피보나치 함수
- 백준 2585
- 백준 1463
- 피보나치 함수
- 백준 1005
- 라피씬
- 라피신
- 백준 boggle
- 백준
- 42서울
- 백준 17143
- C++
Archives
프로그래머의 개발노트
[백준 17143] 낚시왕 (C++) 본문
https://www.acmicpc.net/problem/17143
첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)
둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.
- 출력
낚시왕이 잡은 상어 크기의 합을 출력한다.
- 풀이 (어려웠던 점)
다른건 괜찮았는데, 상어를 움직일 때가 정말 난해한 문제였습니다. 또한 상어가 같은 공간에 있는 경우에 가장 크기가 큰 상어가 나머지 상어를 잡는 구조인데, 처음 생각한 것은 칸에 넣을때 마다 최신화를 해주면 되겠다 였는데, 같은 크기의 상어가 들어왔을때 저장해야 하는 문제가 생겼습니다. 또한 방향을 바꾸는 타이밍을 잘못 계산했고, 루프를 어떻게 돌려야 효율적으로 상어를 이동시킬지에 대한 부분도 깊게 생각을 했습니다.
- 코드
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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 | #include <iostream> #include <vector> #include <algorithm> #define endl "\n" int R, C, M; struct shark { int r,c,d,s,z; int live; }; std::vector<shark> shark_location; std::vector<std::pair<int, int> >direction; std::vector<std::vector<int> >coord; std::vector<std::vector<int> >sharks_save; int ans; int make_reverse_direction(shark sharks) { if (sharks.d == 1) return(2); else if (sharks.d == 2) return(1); else if (sharks.d == 3) return(4); else return(3); } void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { input_faster(); std::cin >> R >> C >> M; shark_location.resize(M+1); direction = {{0,0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}}; // up down right left coord.resize(R+1, std::vector<int>(C+1, 0)); sharks_save.resize((R + 1)*(C + 1)); ans = 0; for (size_t i = 1 ; i <= static_cast<size_t>(M) ; i++) { std::cin >> shark_location[i].r; std::cin >> shark_location[i].c; std::cin >> shark_location[i].s; std::cin >> shark_location[i].d; std::cin >> shark_location[i].z; shark_location[i].live = 1; coord[shark_location[i].r][shark_location[i].c] = i; } } void catch_shark(size_t index) { for (size_t i = 1; i <= static_cast<size_t>(R) ; i++) { if (coord[i][index] >= 1) { shark_location[coord[i][index]].live = 0; ans += shark_location[coord[i][index]].z; break; } } } int shark_reached_max(size_t i) { if (shark_location[i].d == 1 || shark_location[i].d == 2) return (R); else return (C); } void shark_move() { for (size_t i = 1 ; i <= static_cast<size_t>(M) ; i++) { if (!shark_location[i].live) continue; int shark_can_go = shark_location[i].s; int max_val = shark_reached_max(i); int move; while (shark_can_go > 0) { move = max_val - 1; if (shark_location[i].d == 2) move = R - shark_location[i].r; else if (shark_location[i].d == 1) move = shark_location[i].r - 1; else if (shark_location[i].d == 4) move = shark_location[i].c - 1; else move = C - shark_location[i].c; if (shark_can_go - move < 0) move = shark_can_go; shark_can_go-= move; shark_location[i].r += (direction[shark_location[i].d].first * move); shark_location[i].c += (direction[shark_location[i].d].second * move); if (shark_location[i].d == 1 || shark_location[i].d == 2) { if (shark_location[i].r == 1 || shark_location[i].r == R) shark_location[i].d = make_reverse_direction(shark_location[i]); } else { if (shark_location[i].c == 1 || shark_location[i].c == C) shark_location[i].d = make_reverse_direction(shark_location[i]); } } int x = shark_location[i].c; int y = shark_location[i].r; if (coord[y][x]) // already shark is in { if (shark_location[coord[y][x]].z < shark_location[i].z) { for(size_t k = 0 ; k < sharks_save[y * C + x].size(); k++) { shark_location[sharks_save[y * C + x][k]].live = 0; } sharks_save[y * C + x].clear(); sharks_save[y * C + x].push_back(i); coord[y][x] = i; } else if (shark_location[coord[y][x]].z == shark_location[i].z) { sharks_save[y * C + x].push_back(i); } else shark_location[i].live = 0; } else { sharks_save[y * C + x].push_back(i); coord[y][x] = i; } } } void solve() { for(size_t i = 1 ; i <= static_cast<size_t>(C); i++) // man move { catch_shark(i); std::fill(coord.begin() , coord.end(), std::vector<int>(C+1, 0)); // coord initialization std::fill(sharks_save.begin(), sharks_save.end(), std::vector<int>(0)); shark_move(); } } void print_val() { std::cout << ans; } int main() { input(); solve(); print_val(); return (0); } | cs |
'백준 알고리즘' 카테고리의 다른 글
[백준 9095] 1,2,3 더하기 (C++) (0) | 2021.01.21 |
---|---|
[백준 1463] 1로 만들기 (C++) (0) | 2021.01.21 |
[백준 1348] 주차장 (C++) (0) | 2021.01.17 |
[백준 2585] 경비행기 (C++) (0) | 2021.01.17 |
[백준 9202] boggle (C++) (0) | 2021.01.17 |
Comments