문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
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
'Study > Algorithm' 카테고리의 다른 글
[백준] 1302번 베스트셀러 - Node.js/JavaScript (0) | 2022.12.13 |
---|---|
[백준] 1543번 문서 검색 - Node.js/JavaScript (0) | 2022.11.30 |
[프로그래머스] 약수의 개수와 덧셈 - JavaScript (0) | 2022.10.27 |
[백준] 1966번 프린터 큐 - Node.js/javascript (0) | 2022.10.24 |
[백준] 2798번 블랙잭 - Node.js/javascript (1) | 2022.09.23 |