[백준] 1193번 - 분수찾기 [Java][C++]

문제 링크

---

1. 문제 풀이

무한히 큰 배열의 분수들에 대해 지그재그로 순서를 매겼을 때, $X$ 번째 분수를 구하는 문제로 반복문을 활용해 분자가 $1$ 이면 분모가 $1$ 이 될 때까지 좌하 방향으로 순회하고, 분모가 $1$ 이면 우상 방향으로 순회하도록 했다. 이때 끝에 도달하면 우로 한 칸 이동하거나 아래로 한 칸 이동하도록 해줬다.

---

2. 코드

1. 구현 [Java]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int X = Integer.parseInt(br.readLine());

        int numerator = 1;  // 분자
        int denominator = 1;  // 분모
        int order = 1;
        while (order < X) {
            while (order < X && numerator > 1) {
                numerator--;
                denominator++;
                order++;
            }
            if (order == X) break;
            denominator++;
            order++;

            while (order < X && denominator > 1) {
                numerator++;
                denominator--;
                order++;
            }
            if (order == X) break;
            numerator++;
            order++;
        }

        System.out.printf("%d/%d", numerator, denominator);
    }
}

2. 구현 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int x;
    cin >> x;

    int numerator = 1;    // 분자
    int denominator = 1;  // 분모
    int order = 1;
    while (order < x) {
        while (order < x && numerator > 1) {
            numerator--;
            denominator++;
            order++;
        }
        if (order == x) break;
        denominator++;
        order++;

        while (order < x && denominator > 1) {
            numerator++;
            denominator--;
            order++;
        }
        if (order == x) break;
        numerator++;
        order++;
    }

    cout << numerator << '/' << denominator;
}

---

3. 풀이 정보

1. 구현 [Java]

언어	시간	메모리	코드 길이
Java 11	132 ms	16068 KB	907 B

2. 구현 [C++]

언어	시간	메모리	코드 길이
C++ 17	8 ms	2020 KB	710 B

---