[BOJ 23973] 백준 23973번 - 표적지 옮기기
| Zero One Algorithm Contest 2021 풀이 | ||
|---|---|---|
| A | [BOJ 23971] ZOAC 4 | |
| B | [BOJ 23972] 악마의 제안 | |
| C | [BOJ 23973] 표적지 옮기기 | |
| D | [BOJ 23974] 짝수 게임 | |
| F | [BOJ 23976] 문자열 나누기 | |
| G | [BOJ 23977] To Find Password | |
| H | [BOJ 23978] 급상승 |
1. 문제
$23973$. 표적지 옮기기 (Zero One Algorithm Contest 2021 Open Contest C번)
2. 풀이
브루트포스 문제인 것처럼 보이긴 하나, $N$과 $M$의 범위가 $2500$ 이어서 무작정 구현을 하기 전에 좀더 효율적인 탐색방안을 찾아야 한다.
$1$점부터 $10$점까지 정확히 한 번씩 점수를 얻어야 한다. 이때, $10$점 칸은 단 하나만 존재하고 이를 무조건 명중시켜야 하므로, $10$점을 사격이 명중한 칸 하나하나에 놓아보는 방식으로 탐색을 진행할 수 있다.
사격이 명중한 칸의 최대 개수는 $100,000$개이다. 따라서 이를 미리 찾아 놓고 각 칸에 대해서 $19\times 19$의 표적지를 탐색한다고 가정하면, $100,000 \times 19 \times 19 $ $= 36,100,000$ 이므로 시간 내에 충분히 탐색 가능하다.
$9$점 칸들은 $10$점 칸과의 $x$거리, $y$거리 중 적어도 하나의 값이 $1$이다. $8$점 칸들은 $10$점 칸과의 $x$거리, $y$거리 중 적어도 하나의 값이 $2$이다. 이는 $x$거리, $y$거리의 최댓값이 $2$임을 의미하기도 한다.
따라서 사격판 위에 표적지를 올렸을 때, 어떤 위치의 칸에 몇 점이 매칭되는지는 $10$점 칸과의 $x$거리, $y$거리의 최댓값을 통해 알아낼 수 있다.
3. 채점 결과
4. 회고
타이핑 미스로 WA를 받았다.
댓글남기기