[BOJ-1193][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

1

 

예제 출력 1 

1/1

 

예제 입력 2

2

 

예제 출력 2

1/2

 

예제 입력 3

3

 

예제 출력 3 

2/1

 

예제 입력 4 

4

 

예제 출력 4 

3/1

 

예제 입력 5

5

 

예제 출력 5

2/2

 

예제 입력 6

6

 

예제 출력 6

1/3

 

예제 입력 7

7

 

예제 출력 7

1/4

 

예제 입력 8

8

 

예제 출력 8

2/3

 

예제 입력 9 

9

 

예제 출력 9

3/2

 

예제 입력 10

14

 

예제 출력 10 

2/4

 

출처

• 문제를 만든 사람: author6
• 문제의 오타를 찾은 사람: deadlylaid
• 어색한 표현을 찾은 사람: djm03178
• 데이터를 추가한 사람: mj2park

 

알고리즘 분류

• 수학
• 구현

 

문제 출처

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

1193번: 분수찾기

 

문제 해결 방법

• 어렵게 풀었던 문제였다.
• 대각선 라인을 기준으로 분석해보면 다음 그림과 같다.

홀수 라인	- 1번째 라인 : 1/1 - 3번째 라인 : 3/1, 2/2. 1/3 ...
짝수 라인	- 2번째 라인 : 1/2, 2/1 - 4번째 라인 : 1/4, 2/3, 3/2, 4/1 ...

 

• 홀수/짝수 라인 별 분모와 분자의 크기 변화를 비교해보면 다음과 같다.
  • 홀수 라인  : 3/1, 2/2, 1/3, ...
    • 분자 : 1씩 감소한다.
    • 분모 : 1씩 증가한다.
  • 짝수 라인 : 1/4, 2/3, 3/2, 4/1
    • 분자 : 1씩 증가한다.
    • 분모 : 1씩 감소한다.
• 첫 번째 대각선 라인부터 N 번째 대각선 라인까지 포함된 요소들의 전체 개수(totalSum)는 $1 + 2 + 3 + … + N$ 이다. 이것을 코드로 나태내면 다음과 같다.

int N = 0;
while (조건) {
    N++;
    totalSum += N;
}

• 이 과정은 X 값이 포함된 대각선 라인의 원소의 개수가 포함될 때까지 반복해야 하므로, 조건을 totalSum < X로 해준다.
• X 번째의 값을 구하려고 할 때, X 번째의 값이 포함된 대각선 라인까지의 모든 요소의 개수 합(totalSum)에서 X를 뺀 차이값을 order 변수에 할당한다.
  • 이 때, order 변수는 N 번째 대각선 라인에서 몇 번째 숫자인지를 나타낸다.
• 그리고 N 번째 대각선 라인이 홀수 번째 라인인지, 짝수 번째 라인인지 구별하여 분자와 분모의 값이 출력되도록 한다.
  • 홀수 번째 라인
    • 분모의 크기는 1부터 1씩 증가한다.
    • 분자의 크기는 N부터 1씩 감소한다.
  • 짝수 번째 라인
    • 분모의 크기는 N부터 1씩 감소한다.
    • 분자의 크기는 1부터 1씩 증가한다.

 

코드

#include <iostream>
using namespace std;

int X, N, totalSum, order, up, down;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> X;
    
    N = 0;
    while (totalSum < X) {
        N++;
        totalSum += N;
    }

    order = totalSum - X;    // 대각선 라인 안에서 몇 번째 숫자인지 

    if (N % 2 == 1) {    // 홀수 라인인 경우
        up = 1 + order;    // 분자는 1부터 시작한다.
        down = N - order;    // 분모는 N부터 시작한다.
    }
    else {    // 짝수 라인인 경우
        up = N - order;    // 분자는 N에서 시작한다.
        down = 1 + order;    // 분모는 1부터 시작한다.
    }

    cout << up << '/' << down << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [기본 수학 1]
• 브론즈I