[백준 / BOJ] C++ 1193 분수찾기

1193번: 분수찾기

 

문제

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

1193번: 분수찾기

 

 

풀이

나열된 분수는 1/1, 1/2, 2/1, 3/1, 2/2, 1/3,... 과 같은 순서로 이루어져 있다. 순서대로 1번, 2번, 3번,... 분수라고 할 때, X번째 분수를 구하는 문제다.

 

표에서 대각선마다 규칙이 있는데 홀수번째 줄은 위로, 짝수번째 줄은 아래로 향한다. 또 N번째 줄에는 N개의 분수가 있다.

 

따라서 X번째 수가 있는 줄까지 가기 위해 X에서 각 줄마다 있는 분수의 수만큼 빼주다가(X -= line) 더 이상 뺄 수 없을 때까지 줄을 이동한다.

 

그리고 홀수번째 줄일 때는 아래에서부터 시작이고, 짝수번째 줄일 때는 위에서부터 시작이므로 각 줄의 출발지점으로부터 분자는 X번째 수다. 따라서 홀수번째 줄일 때는 분자는 line - X + 1이고 분모는 X, 짝수번째 줄에서는 분자가 X이고 분모가 line - X + 1이다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int x;
  cin >> x;
  int line = 1;
  while (x > line) {
    x -= line;
    line++;
  }
  if (line % 2)
    cout << line - x + 1 << '/' << x << '\n';
  else
    cout << x << '/' << line - x + 1 << '\n'; 
  return 0;
}