[백준 단계별 문제 풀기8] 규칙찾기3 - 분수찾기

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

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

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이고, 1행은 분모가 1이다.

  - 진행되는 방향에 따라 아래로 내려가는 경우 분자 + 1, 분모 - 1, 올라가는 경우 분자 - 1, 분모 + 1

  - 방향이 전환되는 시점은 1, 2, 4, 7, ... 즉 +1, +2, +3, +4, ... 이다.

  - 오른쪽 아래로 내려가는 대각선(1/1, 2/2, 3/3,...) 기준으로 위쪽 테이블과 아래쪽 테이블이 대칭이다.

  - 입력이 1천만 이하 이니까 하나씩 찾아도 O(N) 에는 끝난다. 

2. 코드 작성

#include <iostream>

2

​

3

using namespace std;

4

​

5

int main(int argc, char** argv){

6

  int in;

7

​

8

  cin >> in;

9

​

10

  int a = 0;

11

  int t = 1, b = 1;

12

  for(int i=1; i<=in; i++){

13

    a += i;

14

    if( a - i <= in && in <= a ){

15

      t = i - ( a - in );

16

      b = 1 + ( a - in );

17

      if( (i%=2) == 1 ){

18

        int temp = t;

19

        t = b;

20

        b = temp;

21

      }

22

      break;

23

    }

24

  }

25

​

26

  cout << t << "/" << b;

27

​

28

}

예를들어 9번째의 분수는 3/2 이다. 이 분수는 4/1 과 1/4 사이에 있는 분수이다. 9번째는 i가 4번째 일때 즉 코드의 14번 라인에서 변수 a = 10, 6 <= 9 <= 10 이면 if절이 실행된다.

t = 4 - ( 10 - 9 ) = 3

b = 1 + ( 10 - 9 ) = 2

15, 16라인의 a - in 은 끝에 있는 분수에서 몇 번째 위치에 있는지를 구한 것이다.

그리고 i는 짝수이므로 17번 라인은 실행되지 않는다. 

17번 라인은 사실에서 확인한 방향 전환과 오른쪽 아래로 향하는 대각선 기준으로 대칭이라는 점을 이용해 t, b를 바꾸면 되겠다고 생각하였다.