2021.12.28 8일차

백준 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번째 분수를 구하는 프로그램을 작성하시오.

나의 풀이

f(1) - 1/1 -> 분모, 분자 합: 2
f(2) - 1/2, f(3) - 2/1 -> 분모, 분자 합: 3
f(4) - 3/1, f(5) - 2/2, f(6) - 1/3 -> 분모, 분자 합: 4
f(7) - 1/4, f(8) - 2/3, f(9) - 3/2, f(10) - 4/1 -> 분모, 분자 합: 5

1. 크게 2단계로 분류
2. 합에 해당하는 값 그룹 분류
   1 -> 2, 3 -> 4, 5, 6 -> 7, 8, 9, 10
   -n씩 개수 증가
   -num에 n에 1씩 증가시키면서 1미만될 때까지 빼기
   -group에 1더한 값을 합으로 설정
3. 해당하는 그룹에서 해당하는 값 찾기
   -num에 순서 빼기
   -순서는 num이 1로 시작하면서 1씩 감소
   -order를 2 - num으로 설정
   -분모, 분자는 order와 sum - order로 구하기
4. 합이 짝수일 때 분자가 먼저 큰 수
5. 합이 홀수일 때 분모가 먼저 큰 수

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int num = scanner.nextInt();
        int group = 1;

        while (num > 1) {
            group++;
            num -= group;
        }
        int sum = ++group;
        int order = 2 - num;

        int a; int b;

        if (sum % 2 == 0) {
            a = order;
            b = sum - order;
        } else {
            a = sum - order;
            b = order;
        }

        System.out.println(a + "/" + b);
    }
}

생각하기

• n이 증가하면서 조건 설정