문제
https://www.acmicpc.net/problem/1004
1004번: 어린 왕자
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주
www.acmicpc.net
풀이
출발점에서 도착점으로 이동하면서 행성에 진입하거나, 이탈할 때의 횟수를 구하는 문제입니다.
진입하거나 이탈할 때를 어떻게 알 수 있을까요?
먼저 출발점과 도착점을 그려봅시다.
아무런 행성이 없는 경우, 행성에 진입/이탈 할 필요가 없겠죠??
다음 두 경우에도 행성에 진입/이탈 할 필요가 없을 것입니다.
다음과 같은 경우에 진입/이탈을 해야합니다.
행성이 출발점을 두르고있거나, 도착점을 두르는 경우 진입/이탈을 해야합니다.
이것을 어떻게 표현할 수 있을까요?
출발점 혹은 도착점으로부터 행성의 중심점까지의 거리가 행성의 반지름보다 작다면 행성에 둘러 쌓여있다고 말할 수 있습니다.
하지만 출발점과 도착점이 둘 다 행성에 둘러쌓인경우는 진입/이탈할 필요가 없겠죠??
따라서 출발점만 둘러쌓여있거나, 도착점만 둘러 쌓여있는 경우에 진입/이탈을 시도하게 됩니다.
소스코드로 작성할 때, 두 점사이의 거리는 원래 루트를 씌워주어야 하지만, 루트를 안씌워주고 반지름까지 제곱해서 구하는 방식으로 구현하였습니다.
소스코드
후기
문제가 잘 이해되지 않을 수 있습니다.
저는 예제입력을 직접 그려보면서 이해하는데 도움을 얻었습니다.
행성에 둘러쌓여있는지는 체크하는것이 핵심인 문제였습니다.
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 15650 N과 M (2) (Swift) (0) | 2023.03.20 |
|---|---|
| [BOJ] 백준 15649 N과 M (1) (Swift) (0) | 2023.03.20 |
| [BOJ] 백준 1002 터렛 (Swift) (0) | 2023.03.17 |
| [BOJ] 백준 2477 참외밭 (Swift) (1) | 2023.03.16 |
| [BOJ] 백준 3009 네 번째 점 (Swift) (0) | 2023.03.16 |
