[BOJ1193][C++] 분수 찾기

문제

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

 

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

 

 

출처

· 문제를 만든 사람: author6

· 문제의 오타를 찾은 사람: deadlylaid

· 어색한 표현을 찾은 사람: djm03178

 

 

알고리즘 분류

· 수학

· 구현

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include <iostream> using namespace std;   int main() {     int input, step, lValue, rValue, num, sum = 0;     bool EvenNum;       cin >> input;       for (int i = 1; i <= input; i++) {         sum += i;         step = i;         num = input - sum;         if (sum >= input) {               break;         }     }          EvenNum = (step % 2 == 0) ? true : false;           if (EvenNum == true) {         lValue = 1;         rValue = step;           for (int i = 1; i <= step; i++) {             if (i == step + num) {                 break;             }             else {                 lValue++;                 rValue--;             }         }     }     else {         lValue = step;         rValue = 1;           for (int i = 1; i <= step; i++) {             if (i == step + num) {                 break;             }             else {                 rValue++;                 lValue--;             }         }     }       cout << lValue << "/" << rValue << endl;          return 0; }

---

문제 해결 방법

• 다음과 같은 규칙을 발견하여 문제를 해결하였다.
  • 표에서 한 대각선을 옮겨갈 때마다 step이 증가한다고 가정하였다.
  • step이 홀수 인지 짝수 인지에 따라 규칙이 달라짐을 확인할 수 있었다.
    • 짝수번 step일 때, 각 step의 시작 값 : 1/(step)
    • 홀수번 step일 때, 각 step의 시작 값 : (step)/1
  • 각 step 별로 step 개의 과정이 진행됨을 확인하였다.
    • 예) step이 1 일 경우, 1 단계의 과정 진행
  • 입력을 받은 정수(input)가 몇 번째 step에 있는지 알아낸 후(이 때, 해당 step에서 몇 번째에 있는지도 함께 알아낸다.(num)), 발견한 규칙에 따라 프로그램을 구현하여 결과값을 출력하게 하였다.

[STEP 1: 1] 1개
1 : 1/1  -> [1]/1

[STEP 2 : 2~3] 2개
2: 1/2  -> 1/[2]
3: 2/1

[STEP 3 : 3~6] 3개
4: 3/1 -> [3]/1
5: 2/2
6: 1/3

[STEP 4 : 7~10] 4개
7: 1/4 -> 1/[4]
8: 2/3
9: 3/2
10: 4/1

[STEP 5 : 11~15] 5개
11: 5/1 -> [5]/1
12: 4/2
13: 3/3
14: 2/4                      v
15: 1/5

[STEP 6 : 16~21] 6개
16: 1/6 -> 1/[6]
17: 2/5
18: 3/4
19: 4/3
20: 5/2
21: 6/1