[JavaSrcipt] Baekjoon - 1193 : 분수찾기

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

 

예제입력	예제출력
1	1/1
2	1/2
3	2/1
4	3/1
5	2/2
6	1/3
7	1/4

 

❌ 풀이

문제를 읽고 이전문제 벌집 처럼 총 갯수라던가

혹은 일정하게 증감한다거나 하는 규칙을 찾아보려고

한참을 생각했었는데 이렇다고 할만한 규칙이라고는

분수의 갯수가 한대각선? 한행? 씩 넘어갈때마다

1개씩 증가한다는것 외에는 찾지못했다.

 

 

✅ 다른분의풀이

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim();
let number = Number(input);
let value = 1;
while (true) {
	number -= value;
	if (number <= 0) {
		number += value;
		break;
	}
	value++;
}

if (value % 2 === 1) {
	console.log(`${value - (number - 1)}/${1 + (number - 1)}`);
} else {
	console.log(`${1 + (number - 1)}/${value - (number - 1)}`);

 

value는 대각선행을 나타낸다고 보았다.

while문으로 무한루프하며

number -= value의 값이 0보다 작거나같아질때까지

value 즉 행의값을 하나씩 올렸다.

 

예를들어 입력값이 8일경우

8 -= 1 은 7이고 7<=0조건이 거짓이므로 첫번째행이 아니다. 그러므로 value++하고

7 -= 2 는 5이며 5<=0 조건이 거짓이므로 두번째행역시아니다. value++

5 -= 3 는 2이며 2<=0 조건이 거짓이므로 세번째행도아니다. value++

 

2 -= 4 는 -2로 -2<=0조건이 참이되어 8번째분수는 4번째행에 속한다는것을 알 수 있다.

if(number<=0) 조건이 참이므로 

number인 -2에 value인 4를 더해주며 

 

number=2 value=4의 값을 갖고 while문을 탈출한다.

 

이때 입력값의 분수는 4번째행 2번째자리에 속한다는것을 의미하는데

2번째자리를 셀때 기준이 ↗방향인지 ↙방향인지에 따라 다르다.

 

문제를보면

홀수행은 ↗

짝수행은 ↙ 방향인것을 알 수 있다

위에서 구한 4번째행 즉 짝수행의 2번째는 ↙방향 2번째 2/3을 나타낸다는것이다.

 

if (value % 2 === 1) {
console.log(`${value - (number - 1)}/${1 + (number - 1)}`);
} else {
console.log(`${1 + (number - 1)}/${value - (number - 1)}`);

 

짝수이므로 1+ (2 - 1) 분자 / 4- (2-1) 분모 

2/3을 출력한다.

 

 

 

몇번째 행인지 구하는것까진 이해했는데 

분자값 분모값이 어떻게해서 저 공식을 사용하는지는 완전한 이해는 하지못했다.

 

 

 

 

 

-출처

https://www.acmicpc.net/problem/1193