구현 - 분수찾기

백준 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	…	…	…	…	…
…	…	…	…	…	…

 

다음과 같이 무한히 큰 배열에서 X가 주어졌을 때, X번째 분수를 구해야한다.

분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 가정한다.

 

무한히 큰 배열이 주어졌기 때문에 배열을 만들어서 푸는 문제가 아니라 규칙을 찾아 수식을 세워 구하는 문제이다.

내가 구해야하는 것을 정리하면 다음과 같다.

 

1. X가 어느 범위에 속하는지 구해야한다.

1	2	6	7	15	…
3	5	8	14	…	…
4	9	13	…	…	…
10	12	…	…	…	…
11	…	…	…	…	…
…	…	…	…	…	…

 

분수의 순서를 다음과 같이 지그재그로 표현할 수 있다.

예를 들어 내가 13번째 분수를 구하고 싶다면 13번째가 어느 범위에 속해있는지부터 알아야한다.

 

첫번째 범위 : 1

두번째 범위 : 2 3

세번째 범위 : 4 5 6

네번째 범위 : 7 8 9 10

다섯번째 범위 : 11 12 13 14 15

 

13은 다섯번째 범위에 속해있다.

그렇다면 어느 범위에 있는지 어떻게 찾을 수 있을까?

범위의 가장 마지막 숫자와 비교하면 된다. 13은 10보다 크고 15보다 작기 때문에 13이 다섯번째 범위에 있다는 것을 알 수 있다.

 

2. 범위에서 몇번째 위치에 우리가 찾고자 하는 값이 있는지 계산한다.

1	2	6	7	15	…
3	5	8	14	…	…
4	9	13	…	…	…
10	12	…	…	…	…
11	…	…	…	…	…
…	…	…	…	…	…

 

우리가 구하고자 하는 것은 n번째 영역의 a번째 분수를 구해야한다.

위의 예시대로 5번째 영역인 것은 찾았고 이제 몇 번째 분수인지를 찾아야한다.

5번째 영역의 가장 마지막 번째는 15번째이다. 우리가 구하고자하는 13번째에서 빼면 2가 나온다.

즉, 영역의 마지막 번째와 내가 구하고자 하는 위치 번째는 2만큼의 차이가 나는 것이다.

5번째 영역이면 영역에 속하는 분수의 갯수가 5이기 때문에 5 - 2 = 3 즉, 5번째 영역의 3번째 분수가 우리가 찾고자 하는 값이 된다.

 

이것을 식으로 정리하면 다음과 같다.

a = n - ( end - x )

 

 

3. 해당 위치의 분수를 계산한다.

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	…	…	…	…	…
…	…	…	…	…	…

 

규칙을 찾아보면 범위가 홀수인 것은 분자가 내림차순, 분모가 오름차순이다.

반면에 범위가 짝수라면 분자는 오름차순, 분모는 내림차순이다.

분모 + 분자 = n번째 영역 + 1 이기 때문에

분모 = n번째 영역 + 1 - 분자이다.

이 때, 범위가 짝수라면 분자는 위에서 구한 a를 만족하게 된다. 반대로 홀수라면 분모가 a를 만족하게 된다.

정리를 하면 다음과 같다.

 

1. 범위가 짝수일 때

- 분모 = n + 1 - a

- 분자 = a

 

2. 범위가 홀수일때

- 분모 = a

- 분자 = n + 1 - a

 

이제 코드로 구현을 하면 된다.

 

---

코드 구현

 

const input = Number(require('fs').readFileSync('./input.txt').toString().trim());

function solution(x) {
  let range = 1;
  let end = 1;
  while (end < x) {
    end += range + 1;
    range++;
  }
  let a = range - (end - x);
  if (range % 2 === 0) {
    return `${a}/${range - a + 1}`;
  }
  return `${range - a + 1}/${a}`;
}

console.log(solution(input));

 

 

느낀점

사실 이 문제는 생각보다 어려웠다.

분모와 분자를 구하는 부분과 범위 내에서 몇번째에 속하는 지 찾는 것이 상당히 까다로웠다.

난이도가 그렇게 높은 문제가 아니기에 이것도 풀지 못하나 자책을 했지만 익숙해질 때까지 복습해서 반드시 나의 풀이로 터득해야겠다.

 

참고 블로그

https://codingmyoni.tistory.com/entry/%EB%B0%B1%EC%A4%80-1193-%EB%B6%84%EC%88%98%EC%B0%BE%EA%B8%B0-javascript

[백준] 1193: 분수찾기 (javascript)