[백준] 1193번 분수 찾기 - JAVA(자바)

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

1193번: 분수찾기

문제

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

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

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

예제 입력

7

예제 출력

1/4

---

풀이 과정

배열에서 지그재그 되는 대각선을 위와 같이 k번째 대각선이라고 나타낼 수 있다.

n이 주어졌을 때 k를 구하기 위해서는 n 이전에 원소의 개수가 몇 개인지 찾아야 한다.

이를 위해 팩토리얼 함수 fact()를 만들어 사용하였다.

예를 들어 n = 4이면,

fact(1) = 1, fact(2) = 3, fact(3) = 6이 되어 k가 3이 될 때 fact() 값이 n보다 커지므로 k는 3이다.

public class Main {
    public static void main(String[] args) throws IOException {
        ...
        int k = 1;
        while (n > fact(k)) {
            k++;
        }
        ...
    }

    static int fact(int n) {
        int result = 0;
        for(int i=1; i<=n; i++) {
            result += i;
        }
        return  result;
    }
}

k 값을 구하면 k가 홀수인지 짝수인지에 따라 대각선 방향이 다르기 때문에 이를 나누어 구해준다.

 

k가 홀수일때 분모와 분자의 규칙을 찾아보자.

k = 3인 경우,

n	4	5	6
분모	1	2	3
분자	3	2	1

fact(k-1) = fact(2) = 6이다.

k = 5인 경우, 

n	11	12	13	14	15
분모	1	2	3	4	5
분자	5	4	3	2	1

fact(k-1) = fact(4) = 10이다.

▷ 분모는 fact(k-1) - n 의 규칙을 띄고, 분자는 k + 1 - 분모 의 규칙을 띈다.

 

k가 짝수일때 분모와 분자의 규칙을 찾아보자.

k = 2인 경우,

n	2	3
분모	2	1
분자	1	2

fact(k) = fact(2) = 6이다.

k = 4인 경우, 

n	7	8	9	10
분모	4	3	2	1
분자	4	3	2	1

fact(k) = fact(4) = 10이다.

▷ 분모는 fact(k) - n + 1 의 규칙을 띄고, 분자는 k + 1 - 분모 의 규칙을 띈다.

        if(k%2 != 0) { // k가 홀수이면 아래에서 위로 올라가는 방향
            deno = n - fact(k-1);
            nume = k + 1 - deno;
        }
        else { // k가 짝수이면 위에서 아래로 내려가는 방향
            deno = fact(k) - n + 1;
            nume = k + 1 - deno;
        }

 

코드

이를 종합하여 코드를 작성하면 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int deno = 0; // 분모
        int nume = 0; // 분자

        int k = 1;
        while (n > fact(k)) {
            k++;
        }

        if(k%2 != 0) { // k가 홀수이면 아래에서 위로 올라가는 방향
            deno = n - fact(k-1);
            nume = k + 1 - deno;
        }
        else { // k가 짝수이면 위에서 아래로 내려가는 방향
            deno = fact(k) - n + 1;
            nume = k + 1 - deno;
        }

        sb.append(nume);
        sb.append('/');
        sb.append(deno);

        System.out.println(sb);
    }

    static int fact(int n) {
        int result = 0;
        for(int i=1; i<=n; i++) {
            result += i;
        }
        return  result;
    }
}