백준 1193 : 분수 찾기 - javascript(구현)

문제 출처 

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

1193번: 분수찾기

분수찾기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

256 MB

120616

61084

52516

51.559%

문제

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

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 복사

1/1

예제 입력 2 복사

2

예제 출력 2 복사

1/2

예제 입력 3 복사

3

예제 출력 3 복사

2/1

예제 입력 4 복사

4

예제 출력 4 복사

3/1

예제 입력 5 복사

5

예제 출력 5 복사

2/2

예제 입력 6 복사

6

예제 출력 6 복사

1/3

예제 입력 7 복사

7

예제 출력 7 복사

1/4

예제 입력 8 복사

8

예제 출력 8 복사

2/3

예제 입력 9 복사

9

예제 출력 9 복사

3/2

예제 입력 10 복사

14

예제 출력 10 복사

2/4

문제 풀이 힌트 

주어지는 입력값이 무려 범위가 (1 ≤ X ≤ 10,000,000) 이렇다.

단순 반복문으로 찾는 것은 말이 안된다. 

 

주어진 분수들을 잘 째려보자. 1/11/2 2/11/3 2/2 3/11/4 2/3 3/2 4/1... 

 

그렇다 그룹화할 수 있겠다. 규칙은 분모와 분자를 더했을 때 합이 같다. 첫번째 줄: 분모 + 분자 = 2 두번째 줄: 분모 + 분자 = 3 세번째 줄 : 분모 + 분자 = 4 네번째 줄 : 분모 + 분자 = 5 

 

자 그럼 해당 줄(line) 과 몇번째 분수(count)인지의 규칙은 뭘까? 첫번째 줄 의 시작 분수의 순서 : 1

두번째 줄 의 시작 분수의 순서 : 2

세번째 줄 의 시작 분수의 순서 : 4

네번째 줄 의 시작 분수의 순서 : 7

 => 해당줄 (line)은 +1 씩 늘어나고, 

=> 해당줄의 첫번째 분수의 순서는 현재 count에 현재 line을 더한것만큼 커지고 있다

ex) 

line 1: 1

line2 : 2 3

line3 : 4 5 6

line4: 7 8 9 10

문제 풀이 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input.shift());

function findFraction(x) {
    let line = 1; //몇번째 줄 
    let count = 1; //해당 줄의 첫번째 분수가 몇번째인지  

    while (count + line <= x) {
        count += line; //count는 line이 +1 될 때마다, line을 더한것만큼 커진다. 
        line++; //줄은 계속 +1 이 된다. 
    }

    let numerator, denominator;
    if (line % 2 === 0) {
        numerator = x - count + 1;
        denominator = line - (x - count);
    } else {
        numerator = x - line + 1;
        denominator = line - (x - count) + 1;
    }
    return `${numerator}/${denominator}`;
}

let answer = findFraction(N);
console.log(answer);

Only 문제 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input.shift());

function findFraction(x) {
    let line = 1;
    let count = 1;

    while (count + line <= x) {
        count += line;
        line++;
    }

    let numerator, denominator;
    if (line % 2 === 0) {
        numerator = x - count + 1;
        denominator = line - (x - count);
    } else {
        numerator = x - line + 1;
        denominator = line - (x - count) + 1;
    }
    return `${numerator}/${denominator}`;
}

let answer = findFraction(N);
console.log(answer);

내 추가 풀이 

const N = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
function solution(N){
   let line = 1; 
   let count = 1; 
    while(count + line <= N){
        count += line
        line++; 
    }
    let up, down; 
    if(line % 2 === 0){
        up =  N -count +1;
        down = line - (N - count);
    }else {
        up = line - (N-count); 
        down = N -count +1; 
    }
    return `${up}/${down}`
}
console.log(solution(N))

 

기억하는 ppoint

 

- 문제에서 말한 규칙 (지그재그)에서 벗어나 내가 또 다른 규칙을 찾는다 (분수를 나열해서 그룹핑)

- 반복문을 잘 이용하자. 익숙해질 때까지 계속 반복 

03. Math.pow(2, 3)은 2를 3번 제곱한 값을 반환하므로 8을 반환

  Math.sqrt(100)은 100의 제곱근을 계산하는 것으로, 결과는 10입니다.

04. 반복문 범위에 따라서 정답이 맞고, 틀리고를 당락짓는다. 절대적으로 이해가 필요하다.