[백준] 1193번 분수찾기 - Node.js/JavaScript

문제

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

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/3이 아니라 2/1

2/1 다음은 2/2가 아니라 내려가서 2/1 

그다음 2/2 1/3 하고 안내려가고 옆으로 가서 1/4

그다음 2/3 3/2 4/1 하고 다시 내려가서 5/1 4/2 3/3 2/4 1/5 

그럼 그 다음은? 1/6이겠죵

 

순서를 알고나면 간단한 문제인데 처음엔 순서 이해가 안됐었다ㅠㅠ,,

이렇게 순서를 적어보면 규칙이 있다

1/1 
1/2 2/1 
3/1 2/2 1/3 
1/4 2/3 3/2 4/1
5/1 4/2 3/3 2/4 1/5
1/6 2/5 3/4 4/3 5/2 6/1

7/1 6/2 5/3 4/4 3/5 2/6 1/7

1/8 2/7 3/6 4/5 5/4 6/3 3/7 8/1

 

내가 푼 정답

let x = require('fs').readFileSync('./input.txt').toString()


let cnt = 0


while (x > 0) {
  cnt++
  x -= cnt
}

if (cnt % 2 === 0) {
  console.log(`${cnt + x}/${1 + -x}`)
} else {
  console.log(`${1 + -x}/${cnt + x}`)
}


// 다른 방법

let line = 0;
let maxValue = 0;

//N의 범위의 최대값이 나올 때 까지
while (maxValue < x) {
  line++
  maxValue += line;
}


let idx = x - (maxValue - line);

if (line % 2 == 0) {
  child = idx;
  parents = (line + 1) - child;
} else {
  child = (line + 1) - idx;
  parents = (line + 1) - child;
}

console.log(child + '/' + parents)

 

 

출처

• 문제를 만든 사람: author6
• 문제의 오타를 찾은 사람: deadlylaid
• 어색한 표현을 찾은 사람: djm03178
• 데이터를 추가한 사람: mj2park

알고리즘 분류

• 수학
• 구현