[백준/C++] 1002번. 터렛

문제

1002번: 터렛

---

1. 첫 번째 풀이

사고 과정

- 간단하게 조규현은 A, 백승환은 B, 마린은 마린으로 칭해보자.

- A로부터 반지름이 r1인 원을, B로부터 반지름이 r2인 원을 그릴 수 있다.

- 두 원은 두 점에서 만나거나, 한 점에서 만나거나, 만나지 않거나, 완전히 겹칠 수 있다.

- 완전히 겹치는 경우는 A와 B의 x, y, r이 모두 같아야 성립된다. 이땐 -1을 출력한다.

- x1과 x2, y1과 y2가 같지만, r1과 r2가 다르다면 0을 출력한다.

- 한 점에서 만나는 경우는, r1 + r2가 A, B 사이의 거리와 같은 경우다. 피타고라스 정리를 이용하면 A와 B 사이의 거리를 구할 수 있다. 다만 sqrt 연산은 부하가 크니, 제곱된 상태 그대로 연산을 수행한다.

- 두 점에서 만나는 경우는 r1 + r2가 둘 사이의 거리보다 짧을 경우, 만나지 않는 경우는 r1 + r2가 둘 사이의 거리보다 길 경우다. 4가지 경우에 맞춰 코딩해 보자.

 

1. 있을 수 있는 좌표의 수를 반환하는 함수를 생성한다.

2. x1, y1, r1이 각각 x2, y2, r2와 모두 같다면 -1을 반환한다.

3. x1, y1이 각각 x2, y2와 같고, r1과 r2가 다르다면 0을 반환한다.

4. |x1 - x2|^2 + |y1 - y2|^2로 A, B사이 거리의 제곱을 구한다. r1 + r2의 제곱과 같다면 1을 반환한다.

5. 위 경우와 다르다면 2를 반환한다.

 

코드

#include <iostream>
#include <cmath>
#include <vector>

int chance(int x1, int y1, int r1, int x2, int y2, int r2) {
	if (x1 == x2 && y1 == y2) {
		if (r1 == r2) {
			return -1;
		}

		return 0;
	}
	
	if (pow(x1 - x2, 2) + pow(y1 - y2, 2) == pow(r1 + r2, 2)) {
		return 1;
	}

	return 2;
}

int main() {
	int n;
	std::vector<int> answer;
	std::cin >> n;

	for (int i = 0; i < n; i++) {
		int x1, y1, r1, x2, y2, r2;
		std::cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
		answer.push_back(chance(x1, y1, r1, x2, y2, r2));
	}

	for (auto i : answer) {
		std::cout << i << '\n';
	}

	return 0;
}

 

결과

5일 전인 이유는 블로그 작성 생각 전에 풀었던 문제기 때문

결과는 실패. 입출력엔 문제가 없었다.

---

2. 두 번째 풀이

사고 과정

- 위 과정에서 빼먹은 사례가 있을까?

- 지금까지 난 A와 B 사이에만 마린이 있다고 가정했었다. 만약 A의 원 안에 B의 원이 포함된다면?

- A와 B의 거리가 |r1 - r2|와 같다면 한 점에서, 보다 크다면 두 점에서, 보다 작다면 만나지 않을 것이다.

- 이 사례들도 추가하여 코드를 작성해 보자.

 

코드

#include <iostream>
#include <cmath>
#include <vector>

int chance(double x1, double y1, double r1, double x2, double y2, double r2) {
	// 조규현과 백승환이 같은 위치일 때
	if (x1 == x2 && y1 == y2) {
		// 거리가 같다면 무한대
		if (r1 == r2) {
			return -1;
		}

		// 다르면 0
		return 0;
	}

	// 하나의 원이 다른 하나를 포함할 때, 둘 사이의 거리가 두 원의 반지름 차보다
	int dis = (pow(x1 - x2, 2) + pow(y1 - y2, 2)) - pow(r1 - r2, 2);
	
	// 클 때 (두 점에서 만남)
	if (dis > 0) {
		return 2;
	}

	// 같을 때 (한 점에서 만남)
	else if (dis == 0) {
		return 1;
	}

	// 작을 때 (원이 겹치지 않음)
	else {
		return 0;
	}
	
	// 둘 사이의 거리가 두 원의 반지름 합보다
	dis = (pow(x1 - x2, 2) + pow(y1 - y2, 2)) - pow(r1 + r2, 2);
	
	// 클 때 (원이 겹치지 않음)
	if (dis > 0) {
		return 0;
	}

	// 같을 때 (한 점에서 만남)
	else if (dis == 0) {
		return 1;
	}

	// 작을 때 (두 점에서 만남)
	else {
		return 2;
	}
}

int main() {
	int n;
	std::vector<int> answer;
	std::cin >> n;

	for (int i = 0; i < n; i++) {
		int x1, y1, r1, x2, y2, r2;
		std::cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
		answer.push_back(chance(x1, y1, r1, x2, y2, r2));
	}

	for (auto i : answer) {
		std::cout << i << '\n';
	}

	return 0;
}

 

결과

두 경우를 나누어 코딩해 봤지만, 여전히 실패였다. 그나마 시간 초과가 아닌 점은 다행이다.

---

3. 마지막 풀이

사고 과정

- 차분히 내 코드를 다시 살펴보니, 저 코드엔 큰 문제가 있었다.

- A, B 사이의 거리를 r1 - r2와 비교한 후, 반드시 셋 중 하나로 반환되어 r1 + r2와 비교하지 않는 문제다.

- 이 문제를 해결하려면 r1 - r2와 r1 + r2를 동시에 비교해야 했다.

- 분기를 제대로 정리하기 위해, 수직선을 그려보았다.

 

|r1 - r2| < A, B 사이 거리 < |r1 + r2|일 때 두 점, 둘 중 하나와 같을 때 한 점, |r1 - r2|보다 작거나 |r1 + r2|보다 크면 만나지 않았다.

다시 코드로 정리해보자.

 

코드

#include <iostream>
#include <cmath>
#include <vector>

int chance(double x1, double y1, double r1, double x2, double y2, double r2) {
	// 조규현과 백승환이 같은 위치일 때
	if (x1 == x2 && y1 == y2) {
		// 거리가 같다면 무한대
		if (r1 == r2) {
			return -1;
		}

		// 다르면 0
		return 0;
	}

	// 둘 사이의 거리
	int dis = pow(x1 - x2, 2) + pow(y1 - y2, 2);

	if (pow(r1 - r2, 2) < dis && dis < pow(r1 + r2, 2)) {
		return 2;
	}

	// 같을 때 (한 점에서 만남)
	else if (dis == pow(r1 - r2, 2) || dis == pow(r1 + r2, 2)) {
		return 1;
	}
	
	else {
		return 0;
	}
}

int main() {
	int n;
	std::vector<int> answer;
	std::cin >> n;

	for (int i = 0; i < n; i++) {
		int x1, y1, r1, x2, y2, r2;
		std::cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
		answer.push_back(chance(x1, y1, r1, x2, y2, r2));
	}

	for (auto i : answer) {
		std::cout << i << '\n';
	}

	return 0;
}

 

결과

깔끔하게 문제를 풀었다.

---

개선

사고 과정

- 두 점에서 만나는 분기일 때, pow(r1 - r2, 2) < dis && dis < pow(r1 + r2, 2) 대신 pow(r1 - r2, 2) < dis < pow(r1 + r2, 2)로 줄일 수 있을 것 같다.

 

코드

#include <iostream>
#include <cmath>
#include <vector>

int chance(double x1, double y1, double r1, double x2, double y2, double r2) {
	if (x1 == x2 && y1 == y2) {
		if (r1 == r2) {
			return -1;
		}

		return 0;
	}

	int dis = pow(x1 - x2, 2) + pow(y1 - y2, 2);

	if (pow(r1 - r2, 2) < dis < pow(r1 + r2, 2)) {
		return 2;
	}

	else if (dis == pow(r1 - r2, 2) || dis == pow(r1 + r2, 2)) {
		return 1;
	}
	
	else {
		return 0;
	}
}

int main() {
	int n;
	std::vector<int> answer;
	std::cin >> n;

	for (int i = 0; i < n; i++) {
		int x1, y1, r1, x2, y2, r2;
		std::cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
		answer.push_back(chance(x1, y1, r1, x2, y2, r2));
	}

	for (auto i : answer) {
		std::cout << i << '\n';
	}

	return 0;
}

 

결과

결과는 실패. 왜 실패했을까?

구글링 속도를 100배 줄여준다는 chatGPT에게 관련 질문을 해보았다. GPT의 답변은 아래와 같았다.

a = 5로 초기화한 경우, 조건식 내부에 0 < a < 10을 작성한다면 다음 과정을 거친다. 컴파일러는 우선 0 < a를 실행한다. 이는 참이므로 1(true)을 반환한다. 그럼 식은 다시 1 < 10이 되고, 이는 거짓이 되어 조건문 내용이 실행되지 않는다. 5는 0보다 크고 10보다 작음에도 말이다.

이를 검증하기 위해 추가적으로 구글링해본 결과, 백준에서 다음 글을 찾을 수 있었다.

 

글 읽기 - if문 조건식 안에 부등호 2개 쓰면 안되나요?

이렇게 몰랐던 사실을 하나 더 알게 되었다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/4307344

laywolf님의 코드다.

 

내 코드와 비교

1. cin 대신 scanf를 쓰셨다.

2. x, y, r이 모두 같은 경우 -1을 반환하는 건 똑같지만, 이후 r만 다른 경우는 생략하셨다.

3. x1, y1, r1, x2, y2, r2는 long 형으로, d(거리)는 float 형으로 선언하셨다.

4. 거리를 계산할 때 제곱근으로 구하셨다. 다만 여기서도 sqrt 함수를 쓰는 대신 pow(,,0.5f)를 사용하셨다.

5. else if 조건식에서 ||을 줄내림하여 가독성을 높이셨다.

6. 함수를 따로 구현하지 않고, for문 내에서 입력 후 출력 사이클을 반복시켰다.

 

난 입력값을 모두 받은 후 출력값을 한 번에 출력하는 줄 알았는데, 이 코드를 보니 그게 아닌 듯하다. 이건 내가 백준 스타일을 잘 몰라서 생긴 문제다.

 

실험

입력 후 바로 출력하는 식으로도 통과가 될까?

 

코드

#include <iostream>
#include <cmath>
#include <vector>

int chance(double x1, double y1, double r1, double x2, double y2, double r2) {
	if (x1 == x2 && y1 == y2) {
		if (r1 == r2) {
			return -1;
		}

		return 0;
	}

	int dis = pow(x1 - x2, 2) + pow(y1 - y2, 2);

	if (pow(r1 - r2, 2) < dis && dis < pow(r1 + r2, 2)) {
		return 2;
	}

	else if (dis == pow(r1 - r2, 2) || dis == pow(r1 + r2, 2)) {
		return 1;
	}
	
	else {
		return 0;
	}
}

int main() {
	int n;
	std::cin >> n;

	for (int i = 0; i < n; i++) {
		int x1, y1, r1, x2, y2, r2;
		std::cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
		std::cout << chance(x1, y1, r1, x2, y2, r2) << '\n';
	}

	return 0;
}

 

결과

충분히 가능했다. 이러면 굳이 출력값을 저장해뒀다가 내보내지 않아도 된다

---

강평

경우의 수를 잘 찾는다면 쉽게 풀리는 문제였다. 푸는 과정에서 새로운 지식(0 < a < 10)을 획득했고, 백준에도 좀 더 익숙해졌다.