분수 찾기

내가 작성한 코드 (cpp)

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    int des = 0;
    int x = 1, y = 1;
    for (int i = 1; i < n; ++i) {
        if (des == 0 && x != 1) {
            --x;
            ++y;
        } else if (des == 0 && x == 1) {
            ++y;
            des = 1;
        } else if (des == 1 && y != 1) {
            ++x;
            --y;
        } else if (des == 1 && y == 1) {
            ++x;
            des = 0;
        }
    }
    cout << x << '/' << y << endl;
    return 0;
}

고민한 사항

증가하는 방식에 대해서 규칙을 찾고자 하였다.
1. 홀수라인은 오른쪽으로 올라가고 짝수라인은 왼쪽으로 내려간다.
2. 분모와 분자는 2차배열의 index이다.
3. 한줄 씩 증가할 때 한줄의 개수는 1씩 증가한다.

위의 규칙을 적용한 코드

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    int line = 0;
    int maxIdx = 0;
    int gap = 0;
    while (maxIdx < n) {
        ++line;
        maxIdx += line;
    }
    gap = maxIdx - n;
    if (line % 2 == 0) {
        cout << line - gap << '/' << gap + 1 << endl;
    } else {
        cout << gap + 1 << '/' << line - gap << endl;
    }
    return 0;
}

코드 길이 감축 539B -> 414B
시간 12ms -> 0ms

시간 감축의 가장 큰 이유는 n 만큼 for문을 도는 것이 아닌 n이 해당되는 라인의 마지막 index를 빠르게 찾아 분자, 분모 값을 구하였기 때문이다.