[백준] 1193번: 분수찾기

22 Oct 2018

Reading time ~2 minutes

문제

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

default

이와 같이 나열된 분수들을 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
2	1/2
14	2/4

풀이

처음에 문제를 잘못 이해해서 1/1 -> 1/2 -> 2/1 -> 1/3 -> 2/2 -> 3/1 -> … 이렇게 오른쪽 위에서 왼쪽 아래로 계속 진행된다고 생각했다.

도대체 어디가 틀린건지 한참 고민하다가 방향이 지그재그라는 것을 깨닫고 적용했더니 패스.

#include <iostream>
using namespace std;

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

    int a = 1;
    int n = 0;
    for (n = 0; ; n++) {
        if (a <= num && num <= a + n)
            break;
        else
            a += n + 1;
    }
    
    int numerator = 1;
    int denominator = ++n;
    bool direction = (n % 2 == 0);
    for (int i = 0; i < n; i++) {
        if (direction && a + i == num) {
            cout << numerator << "/" << denominator;
            break;
        }
        else if (!direction && a + n - i - 1== num) {
            cout << numerator << "/" << denominator;
            break;
        }
        else {
            numerator++;
            denominator--;
        }
    }
    return 0;
}

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