[백준] 1193

분수찾기

문제

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

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

풀이

const fraction = () => {
  let input = parseInt(
    require("fs").readFileSync("/dev/stdin").toString().trim()
  );
  let left = 1;
  let right = 1;
  let n = 1;
  let i = 1;
  while (1) {
    if (i === input) break;
    if (n % 2 && left === 1) right = ++n;
    else if (!(n % 2) && right === 1) left = ++n;
    else {
      left += n % 2 ? -1 : 1;
      right += n % 2 ? 1 : -1;
    }
    i++;
  }
  console.log(`${left}/${right}`);
};

fraction();

반성회

규칙

• n은 몇 번째 대각선인지 나타냄
  • n이 짝수일 경우 우상단에서 좌하단으로 이동
  • n이 홀수일 경우 좌하단에서 우상단으로 이동

• i는 언제 반복문을 빠져나갈 지 결정
  • 매 반복문마다 증가하며, 입력값과 같아지면 탈출
• left는 분수의 분자
  • n이 짝수일 경우 1부터 시작하여 1씩 증가하며, 마지막엔 n이 된다
  • n이 홀수일 경우 n부터 시작하여 1씩 감소하며, 마지막엔 1이 된다
• right는 분수의 분모
  • n이 짝수일 경우 n부터 시작하여 1씩 감소하며, 마지막엔 1이 된다
  • n이 홀수일 경우 1부터 시작하여 1씩 증가하며, 마지막엔 n이 된다

따라서

• n이 짝수일 땐
• right가 1이 되었을 때 n을 1 증가시키고, left를 ++n으로 초기화
• n이 홀수일 땐
• left가 1이 되었을 때 n을 1 증가시키고, right를 ++n으로 초기화

i가 입력값과 같아지면 반복문을 탈출하고, 그 때까지 계산된 left와 right (분자와 분모) 를 출력