[JS] 백준 1193번 분수 찾기

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

1193번: 분수찾기

 

원하는 값을 얻기 위해서는

시작값을 지정해주고, 반복문 또는 조건문을 감싸는 반복문을 통해 원하는 값이 나올 때 까지 시작값을 계속 업데이트 하는 방법이 있고,

패턴을 파악하여 원하는 데이터를 단번에 찾아내는 방법 이렇게 두 방법이 있는 것 같다. 

 

전자는 반복문을 통해 차곡차곡 데이터를 계산해야 하지만

후자는 시작값을 계속적으로 업데이트하며 결과값이 나올 때 까지 반복하는 것이 아기 때문에 원하는 값을 얻어내는 시간이 짧고 속도도 빠르다.

 

반복문을 통해 차곡차곡 데이터를 계산해도 되지만, 대부분의 문제의 경우 후자처럼 하라는 출제 의도를 가지고 있으니 원하는 값을 빼내는데 필요한 몇가지 패턴(힌트)를 우선적으로 파악하는게 가장 중요해 보인다.

 

이 문제에서 원하는 값을 얻어내기 위해서는 세 가지 힌트만 알면 된다.

두번째로, n번째 열마다 n개의 값이 존재한다는 것

 

 

 

첫번째로, 각 줄의 분자 분모의 합은 줄 번호+1이라는 것

 

 

세번째로 각 줄마다 진행 방향이 다르다는 것. 홀수번째 줄은 아래에서 위로, 짝수번째 줄은 위에서 아래로 진행한다.

 

 

위의 세 힌트들을 가지고 만약 입력값이 13일 때 어디에 위치하는지 파악할 수 있다.

 

첫번째 힌트에 따라 13번째 데이터는 5번째 줄에 존재한다. 5번째 줄은 15번째까지의 데이터를 가지고 있을 수 있으므로(1+2+3+4+5).

그래서 다섯번째 줄의 세 번째 위치에 13번째 데이터가 존재할 것이다.

 

두번째 힌트에 따라 분자와 분모의 합이 6인 라인에 있다. 그 라인의 시작 데이터는 1/5 또는 5/1 일 것이다. 

 

세번째 힌트에 따라 5/1에서 시작한다.

 

따라서 13번째 데이터는 5/1에서 시작하는 줄의 세 번째 위치의 값이므로 3/3임을 알 수 있다. 

 

이를 코드로 만들면 된다.

 

 

- 내 방법

let input = +require('fs').readFileSync('dev/stdin').toString().trim()
let topNum;
let botNum;
let line = 0;

// 라인 업데이트
while (input > 0) {
  line++;
  input -= line;
}

// 라인에서의 위치 구하기
let linePosition = line + input; // input은 현재 음수이므로

// 라인의 방향 고려해서 topNum, botNum 구하기
if(line % 2 === 1){
  topNum = line;
  botNum = 1;
  for(let i=0; i<linePosition-1; i++){
    topNum--;
    botNum++;
  }
}

if(line % 2 === 0){
  topNum = 1;
  botNum = line;
  for(let i=0; i<linePosition-1; i++){
    topNum++;
    botNum--;
  }
}
console.log(`${topNum}/${botNum}`)