[백준/C++] 1072번. 게임

문제

1072번: 게임

---

1. 첫 번째 풀이

사고 과정

- 가장 간단하게 가보자.

- int x, y를 입력받고

- int winrate = y / x

- 반복문을 돌리면서, (y + 1) / (x + 1)이 winrate와 달라질 때까지 증가

- i 출력

 

코드

#include <cstdio>

int main() {
	long long int x, y;
	scanf("%lld %lld", &x, &y);
	int winrate = (y * 100) / x;

	if (winrate == 100) {
		printf("-1");
		return 0;
	}

	for (int i = 1; i < 1000000000; i++) {
		if ((y + i) * 100 / (x + i) != winrate) {
			printf("%d", i);
			break;
		}
	}
}

 

결과

역시나 시간 초과.

---

2. 두 번째 풀이

사고 과정

- 브루트포스 외의 방법을 찾아야 한다.

- 판수가 늘어도 변하지 않는 것. 그것은 바로 y - x. 이걸 이용할 수 있을까?

- 새 y, x를 나눠 승률을 구했을 때, 기존 승률 + 1이 되면 된다.

- 방정식으로 써보면 100y / x = w이고, 또 (100(y + i)) / (x + i) = w + 1이다.

- 뒤쪽 식을 풀어 i에 대해 정리해 보자.

• (100y + i) / (x + i) = w + 1
• (100y + i) = (w + 1)(x + i)
• 100y + i = wx + x + wi + i
• 100y = wx + x + wi
• wi = 100y - wx - x
• i = (100y / w) - x - x / w

- 근데 굳이 각 항을 w로 나눌 필욘 없어 보이니

• i = (100y - wx - x) / w

- 를 써보자.

- 잠깐만. 저기서 100y / x = w를 대입하면 어떻게 되는 거지?

• i = (100y - 100y - x) * x / 100y
• i = -x^2 / 100y

- 뭔가 기상천외해졌는데?

- 그럼 이번엔, (100(i - (x - y))) / i = w + 1을 이용해 식을 풀어보자. 분자와 분모의 차가 일정하다는 걸 이용한다. 이때 i는 전체 판 수다.

• 100i - 100x + 100y = wi + i
• 99i - wi = 100x - 100y
• (99 - w)i = 100(x - y)
• i = 100(x - y) / (99 - w)

- 첫 번째 식과 동일한 결과가 나왔다. 소수점 단위로 표현이 되며, 판 수는 정수기 때문에 ceil 함수를 씌우면 될 것 같다. i - x로 추가한 판 수를 구할 수 있다.

- 여러 예제를 테스트하던 중, 한 판 더 이겼을 때 승률이 2 이상 오르는 반례를 찾아냈다. 예를 들어, 5판 중 4판을 이겼을 때, 현재 승률은 80이다. 한 판 더 이기면 승률은 83프로까지 오른다.

- 한 판만 더 진행해도 되는 경우는, 현재 판 수가 99판 이하일 때다. 따라서 이 경우는 따로 빼준다.

- 그러나 코드를 고치다가, ceil 함수가 제대로 적용되니 해당 조건은 무시해도 됐다.

 

코드

#include <cstdio>
#include <cmath>

int main() {
	double x, y;
	scanf("%lf %lf", &x, &y);
	int w = (y * 100) / x;
	double i = (100 * (x - y) / (99 - w));
	int c = (int)std::ceil(i) - x;

	printf("%d\n", w);
	printf("%lf\n", i);
	printf("%d", c);
}

빠른 이해를 위한 코드.

 

#include <cstdio>
#include <cmath>

int main() {
	double x, y;
	scanf("%lf %lf", &x, &y);
	int c = (int)std::ceil((100 * (x - y) / (99 - (y * 100) / x))) - x;
	printf("%d\n", c);
}

실제로 제출한 코드

 

결과

이런...

---

3. 세 번째 풀이

사고 과정

- 수식에 정신이 팔려, x == y를 걸러내지 않았다. 이런.

 

코드

#include <cstdio>
#include <cmath>

int main() {
	double x, y;
	scanf("%lf %lf", &x, &y);

	if (x == y) {
		printf("-1");
		return 0;
	}

	int c = (int)std::ceil((100 * (x - y) / (99 - (y * 100) / x))) - x;
	printf("%d\n", c);
}

 

결과

그래도 결과는 틀렸다. 그냥 수식에 문제가 있나 보다.

---

4. 마지막 풀이

사고 과정

- 하지만 이 문제는, 의외의 곳에서 허무하게 정답이 나왔다.

 

코드

#include <cstdio>
#include <cmath>

int main() {
	double x, y;
	scanf("%lf %lf", &x, &y);
	int w = (y * 100) / x;

	if (x == y || w >= 99) {
		printf("-1");
		return 0;
	}

	double i = (100 * (x - y) / (99 - w));
	int c = (int)std::ceil(i) - x;

	printf("%d", c);
}

이는 내가 제출한 코드다. 어떤 코드인지 알겠는가? 두 번째 풀이에서 만든, 첫 번째 코드다.

실제로 제출할 땐 간결한 작성을 위해 w, i를 없애고 c에 몰빵 했었는데, 굳이 굳이 나눠주니 코드가 멀쩡하게 돌아갔다.

 

결과

이 코드를 넣어보게 된 건, x = 327, y = 308이라는 반례를 찾았을 때였다.

해당 값의 정답은 53인데, 내가 압축한 코드엔 68이라는 널뛰는 값이 나왔다.

그래서 혹시나 싶어 위 코드에 돌려보니 53이 나왔고, 거기에 반례를 추가한 뒤 제출하여 정답을 맞힐 수 있었다.

---

가장 효율적인 코드

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

kjo7811님의 코드. 왜 굳이 이분의 코드를 가지고 왔냐? 라 함은, 메모리 156 KB의 극한의 효율 코드는 내가 해석하기엔 너무 깊고, 192 B의 짧은 코드는 외계어 수준이라 줄 나눔을 다 해줘야 하기 때문이다. 알고리즘을 비교하려는 입장에서, 읽기 쉽고 파악하기 좋은 코드가 짱이다.

 

코드 분석

- 이 분의 코드는 입력값이 계속 들어오는 걸 상정해 for(; ~scanf ;)를 사용하셨다. 해당 반복문 내부를 살펴보면 될 것 같다.

- a, b와 함께 수식으로 풀어내셨다. x = 10, y = 8인 경우를 통해 분석해 보자.

• a =  (100 * 8) - (10 * 81) = -10
• b = 80 - 99 = -19
• z = -10 / -19 = 10 / 19 = 0
• a%b = 10, 0 이상이므로 z++
• z = 1, 출력

- 값이 작아서 그런가? 100 80으로 해보자.

• a = (100* 80) - (100 * 81) = -100
• b = 80 - 99 = -19
• z = -100 / -19 = 100 / 19 = 5
• a%b = 5, 0 이상이므로 z++
• z = 6, 출력.

- 이제야 윤곽이 보인다. 정리하면 아래와 같다.

- 승률(z)은 100 * y / x로 구할 수 있다. 여기에 z대신 z + 1을 집어넣어, 다음 승률이 되기까지 필요한 값 a를 구한다.

- b는 z - 99. 99 - z가 아닌 이유는 a가 음수이기 때문.

- 이후 z = a / b가 되고, 이때 z는 더 해야 하는 판 수가 된다.

- 하지만 a%b > 0, 즉 나머지가 있을 경우, 나머지를 채우기 위해 한 판을 더 해야 한다. 따라서 z++을 진행한다.

- 그 결과 추가 판 수가 출력된다.

 

내 코드와 비교

1. 승률을 z로 두셨다. (나는 w)

2. z > 98을 통해 99, 100인 경우를 한 번에 걸러내셨다.

3. 나는 ceil 함수를 통해 소수점을 올렸고, 이 분은 if(a%b)를 통해 소수점을 올리셨다. 이 방법이 훨씬 깔끔해 보인다.

4. 수식은 은근히 같은 결이 있다.

• 나의 경우 (100 * (x - y) / (99 - w)를 통해 (늘어난) 전체 판 수를 구했다.
• 이 분은 (100 * y) - (x * (z+1)) / (z - 99)를 통해 (진행해야 하는) 추가 판 수를 구하셨다.
• 부호와 변수까지 맞추면 더 비슷하다. (x * (w+1) - (100 * y)) / (99 - w)

5. 나는 x, y를 double로, 이 분은 long long으로 받으셨다. 나는 ceil 함수를 사용하기 위해 double로 받았고, 이 분은 나머지를 통해 계산하기 때문에 정수로 받으신 듯하다.

---

강평

자료형이 제일 어려웠던 문제. 나는 단순히 코드를 압축했다 생각했지만, 내부 연산은 다르게 진행되었다. w는 int로, i는 double로 끊어 계산할 땐 제대로 값이 나왔지만, 이를 한 데 모아 계산할 땐 결과가 int로 나왔었나 보다. 그래서 정확하지 않은 계산이 됐고, 결국 틀리게 되었다.

제일 무서운 건, 예제는 전부 똑같이 연산됐다는 점이다. 보이지 않는 곳에서 이런 차이가 발견되니 생각 외로 많이 헤매게 되었다. 간결함보단 정확한 코드 구현을 위해, 변수를 많이 쓰더라도 제대로 구현해야겠다.