[백준] 1193번 분수찾기 C++ 문제 풀이 수학 1

문제

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

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

14

---

예제 출력 1

2/4

---

문제 풀이

#include <iostream>

using namespace std;

int main() {
  int X;
  cin>>X;

  int a = 0;
  int i = 1;
  for(; a<X; i++){
    a+=i;
  }
  i--;
  int numerator;
  int denominator;
  int t = a-X;
  if(i%2 == 1){
    numerator = 1+t;
    denominator = i-t;
  }
  else{
    numerator = i-t;
    denominator = 1+t;
  }

  cout<<numerator<<"/"<<denominator<<'\n';
}

좌상우하 방향으로 분수가 진행됩니다.

최상단 부분에서 분모의 값이 바뀌려면 1/(i-1) 위치에서 i 번 진행해야 분모가 바뀌는 것을 알 수 있습니다.

 

입력받은 값이 어느 구간에 위치하는지 파악해야 합니다. 규칙을 보면

i/1부터 1/i까지 그룹은 i 개로 이루어져 있습니다.

고로 1부터 i까지의 합이 입력받은 값 X보다 클 경우 X는 i/1과 1/i 사이에 위치하게 됩니다.

1부터 i까지의 합인 a에서 입력값 X를 뺀 t는 해당 구간의 시작 지점부터 몇 칸 이동해야 하는지를 나타냅니다.

 

i가 홀수인지 짝수인지에 따라 진행 방향이 다르므로 판별 후 홀수는 아래로, 짝수는 위로 진행하므로

알맞게 t 값을 더하거나 빼고 출력하면 됩니다.

 

 

 

 

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

1193번: 분수찾기