BOJ1193

BaekJoon 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)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

나의 첫번째 답

#include <iostream>

using namespace std;

string whereIam(int num) {

    int curr = 1;
    int row = 1;
    int col = 1;

    while(num != curr) {

        if(row == 1) {      // 1행 
            if(col % 2 == 1) { col++; curr++; continue; } 
            else { row++; col--; curr++; continue; }
        } 
        else if(col == 1) {     // 1열
            if(row % 2 == 0) { row++; curr++; continue; }    
            else { row--; col++; curr++; continue;}
        }
        else{
            if((row + col) % 2 == 0) { row--; col++; curr++; continue; }
            else {row++; col--;  curr++; continue; }
        }
    }

    return to_string(row) + "/" + to_string(col);
}

int main() {

    int input;
    cin >> input;

    cout << whereIam(input) << endl;

    return 0;
}

우선 문제의 조건은 다음과 같은 순서로 분수에 숫자를 매겼었다.

보다보니 분수들의 분자와 분모가 각각 행, 열과 같다는 생각이 들었고,

처음의 1행1열의 칸에서 시작해, 위 사진에서 화살표가 가리키는 순서대로 행렬 위를 지그재그로 순회하면 되겠다고 생각했다.

그래서 위와 같이 작성했다.

백준에서도 정답이라고 했지만, 적어도 문제에서 의도하는 바는 이것이 아니라고 생각해서 좀 더 나은 답을 찾았다.

배열을 다시 보면, (왼쪽 하단에서 오른쪽 상단으로 향하는) 한 대각선 상의 분수들은 모두 분자와 분모의 합이 같다.

대각선에 레벨이란 개념을 만들고, 분자와 분모의 합이 이것과 동일하게하자.

그러면 (입력받았던 숫자)를 이 레벨을 1에서부터 점점 키워가며 반복해서 빼준다면, (입력받았던 숫자)가 레벨보다 낮은 순간이 올 것이다.

레벨은 동시에 그 대각선에 들어가는 분수의 갯수와 같기 때문에.

그 순간을 찾는다면, (대각선의 레벨, 입력받았던 숫자)는 분수의 위치를 특정하기에 충분할 것이다.

그러면 레벨의 홀수, 짝수만 구분하면 두 숫자를 이용해 분자와 분모를 찾을 수 있을 것이다.

두번째 답

#include <iostream>

std::string findFraction(int x) {
    int level = 1; // 현재 대각선의 레벨 (분자와 분모의 합)
    while (x > level) {
        x -= level;
        level++;
    }

    int numerator, denominator;
    if (level % 2 == 1) {
        // 홀수 레벨: 왼쪽 아래로 이동. 분자가 크고 분모가 작아짐
        numerator = level - x + 1;
        denominator = x;
    } else {
        // 짝수 레벨: 오른쪽 위로 이동. 분자가 작아지고 분모가 커짐
        numerator = x;
        denominator = level - x + 1;
    }

    return std::to_string(numerator) + "/" + std::to_string(denominator);
}

int main() {
    int input;
    std::cin >> input;
    std::cout << findFraction(input) << std::endl;
    return 0;
}

기존의 답과 비교하면 약간의 메모리와 시간을 절약할 수 있었다.

코드의 가독성과 길이를 고려했을 때, 확실히 두번째 방법이 더 직관적이어서 나은 방법인 것 같다.