-
[백준] 27583번: Hunt the Wumpus - C++개발/알고리즘 & PS 2024. 8. 27. 01:09
https://www.acmicpc.net/problem/27583
영어 문제니 간단하게 요약해보면
- $10 \times 10$ 크기의 그리드에 4개의 Wumpus 가 있다.
- 정수 $s$를 규칙에 맞춰 업데이트하고, 아래 2자리를 각각 $x, y$좌표로 삼는다.
- 주어진 입력의 좌표로 이동했을 때 wumpus가 있다면 wumpus를 잡았다고 출력한다.
- 가장 가까이 있는 wumpus의 맨해튼 거리를 (있다면) 출력한다.
조심해 주어야 할 부분은 "The first four distinct numbers generated" 즉, $s$에서 wumpus의 위치를 만들 때 똑같은 위치가 나오면 안된다는 것이다.(당연한 건데 이걸 놓쳐서 정답률 100% 문제였는데 오답을 제출해 버렸다 ㅜㅜ).
wumpus 위치 구하기
$s$를 $s + \left\lfloor \frac{s}{13} \right\rfloor + 15$로 업데이트 하고 아래 2자리를 저장한다.
for (int i = 0; i < 4; i++) { do { s = s + s / 13 + 15; loc[i] = s % 100; } while (find(loc, loc + i, loc[i]) != loc + i); }
최대 4개 밖에 없으니 완전탐색해 중복을 체크해주었다.
참고로 아래 두자리를 그대로 저장했으니 거리는 아래와 같이 구할 수 있다.
int dist(int a, int b) { return abs(a / 10 - b / 10) + abs(a % 10 - b % 10); }
이동 처리
이제 이동이 발생할 때마다 현재 위치에 wumpus가 있는지 검사하고 가장 가까운 발견하지 못한 wumpus와의 거리를 출력하면 된다.
전체 코드
#include <iostream> #include <algorithm> using namespace std; int dist(int a, int b) { return abs(a / 10 - b / 10) + abs(a % 10 - b % 10); } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); long long s; cin >> s; int loc[4], hitCnt = 0, m = 0; bool hit[4] = {}; for (int i = 0; i < 4; i++) { do { s = s + s / 13 + 15; loc[i] = s % 100; } while (find(loc, loc + i, loc[i]) != loc + i); } while (hitCnt < 4) { int x; cin >> x; m++; for (int i = 0; i < 4; i++) { if (!hit[i] && loc[i] == x) { cout << "You hit a wumpus!\n"; hit[i] = true; hitCnt++; break; } } int near = 100; for (int i = 0; i < 4; i++) if (!hit[i]) near = min(near, dist(x, loc[i])); if (near == 100) break; cout << near << '\n'; } cout << "Your score is " << m << " moves.\n"; }
'개발 > 알고리즘 & PS' 카테고리의 다른 글
[백준] 30022번: 행사 준비 - C++ (0) 2024.09.02 [백준] 2900번: 프로그램 - C++ (0) 2024.08.27 [BOJ] 20365 블로그2 - C++ (0) 2024.04.07 최소 신장 트리 (MST) (0) 2024.04.04 [BOJ] 2143 두 배열의 합 - C++ (1) 2024.04.04