[백준/C++] 1193번. 분수찾기

문제

1193번: 분수찾기

---

1. 첫 번째 풀이

사고 과정

- 대각선이지만 굳이 대각선으로 볼 필욘 없다. 1/1을 한 줄, 1/2와 2/1을 한 줄, 1/3과 2/2와 3/1을 한 줄. 이렇게 계단처럼 쌓을 수 있다.

이렇게 보면 좀 더 쉽더.

 

- 우린 각 줄의 첫번째, 즉 1/N이 몇 번째부터 시작하는지 알 수 있다. 1, 2, 4, 7, 11. 정확히는, 해당 줄의 앞이 몇 번으로 끝났는지 알 수 있다. 0, 1, 3, 6, 10, 15, 21. 익숙한 1부터 n까지의 합. 이 번호들을 기준 번호라고 하자.

- 그러니 우선 1부터 더해가며, X를 넘지 않는 값까지 더하면, 마지막에 더한 값으로부터 N을 알 수 있다. 만약 12라면 10에서 끝났을 것이고, 5를 더하다 종료되었을 것이다. 1/5는 11번째 값이다.

- 이후 X - (기준 번호)로 몇 칸 떨어졌는지 알 수 있다. 여기선 1칸 떨어졌다. 이를 분자에 더하고 분모에서 빼면 2/4가 나온다.

 

1. x를 입력받는다.
2. 1부터 자연수를 차례대로 더한다. 이 수가 x보다 커질 때 종료한다.
3. 이때, 마지막에 더한 숫자가 1/N의 분모이며, 더하기 직전 수가 기준 번호다.
4. (X - 기준 번호)를 분자에 더하고, 분모에서 뺀다.

 

코드

#include <iostream>

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

	int sum = 1, i = 0;
	while (sum <= 10000000) {
		if (sum + ++i > x) {
			break;
		}
		sum += i;
	}

	int s = x - sum;
	int numerator = 1 + s, denominator = i - s;

	std::cout << numerator << "/" << denominator;
}

 

결과

코드는 생각대로 돌아갔지만, 틀렸다.

---

2. 마지막 풀이

사고 과정

- 문제를 잘못 봤다. 지그재그의 순서가 항상 위에서 내려오는 게 아니었다.

- 하지만 해결법은 간단하다. 1/n의 n이 홀수인 경우, 분모와 분자를 뒤집으면 되니까.

 

코드

#include <iostream>

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

	int sum = 1, i = 0;
	while (sum <= 10000000) {
		if (sum + ++i > x) {
			break;
		}
		sum += i;
	}

	int s = x - sum;
	int numerator = 1 + s, denominator = i - s;

	if (i % 2 == 0) {
		std::cout << numerator << "/" << denominator;
	}
	else {
		std::cout << denominator << "/" << numerator;
	}
}

 

결과

성공했다.

---

가장 효율적인 코드

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

수많은 숏코딩 사이 한 줄기 빛과 같은 nhattlongg님의 코드. 짧고 간결한데 의미 파악도 쉽다.

 

내 코드와 비교

- 원리는 같지만, 구현하는 방식이 달랐다.

1. 나는 sum을 선언하고 i를 더하는 식으로 계산했지만, 이 분은 단순히 입력받은 n에서 i를 빼가며 계산했다.
2. n의 값이 직접 줄어들었으니, 이를 곧바로 분자(또는 분모)에 사용할 수 있게 되었다. 그래서 새 변수도 필요 없다.
3. 남은 한 쪽은 i+1-n이라는 단순한 연산으로 구해냈다.

---

강평

세상은 넓고, 천재는 많다. 내 코드를 되돌아보면 중복되는 연산과, 불필요한 변수가 너무 많았다. 역시 피드백은 성장의 지름길이다.