[ 백준 ] [ JAVA ] 1193 분수 찾기

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

1193번: 분수찾기

 

해당 문제를 풀기 위해서 우리가 알아야할 정보는 무엇일까?

 

x번째의 값을 알기 위해서는 속해있는 Group이 몇 번째인지, 짝수인지 홀수인지 알아야 한다.

다음으로는 이전 Group까지의 분수 개수를 알아야한다.

그래야 해당 Group의 처음 Index를 기준으로 x의 위치를 알고 값을 알 수 있기 때문이다.

 

우선

주어진 문제에 배열을 살펴보자

위 사진처럼 홀수, 짝수 그룹으로 묶어서 확인해보면 군수열이 보일 것이다.

군수열이란 ?
수열을 n개의 항씩 묶어서 규칙성을 가진 군으로 나눈 수열

EX )

1, 1, 2, 1, 2, 3, 1, 2, 3, 4 --> (1), (1, 2), (1, 2, 3), (1, 2, 3, 4)
                                              1군   2군       3군            4군

이런 식이다.

다시 문제로 돌아와서 4G (편의상 그룹을 G로 명명하겠다.)을 분모, 분자 각각 수열로 나타내면

분자 : Child -> C

분모 : Parent -> P

 

우선 공통적으로 N_Group의 분수 개수는 N개이고, 분모 분자 각각 최대값도 N이고 최소값은 1이다.

 

짝수 G

수열 {C} : 1, 2, 3, 4
수열 {P} : 4, 3, 2, 1

등차수열이 보일 것이다.

수열 {C}는 공차가 1인 등차수열이고

수열 {P}는 공차가 -1인 등차수열이다.

 

이번엔 5G를 보자

홀수 G

수열 {C} : 5, 4, 3, 2, 1
수열 {P} : 1, 2, 3, 4, 5

마찬가지로 등차수열이다.

하지만 짝수G와는 반대로

수열 {C}의 공차가 -1이고

수열 {P}의 공차가 1이다.

 

그리고 문제의 지문을 빌려

순서대로 분수를 나타내자면

1/1   1/2   2/1   3/1   2/2   1/3 ...

즉 짝수G는 남서 방향으로 진행하고

홀수 G는 북동 방향으로 진행된다.

 

x가 N_Group의 요소라고 할 때, N을 어떻게 구하냐?

간단하다.

등차수열 합의 공식을 이용해서 구하면 된다.

왜 등차수열 합의 공식?

아래 표를 보자.

1	2	6	7	15
3	5	8	14
4	9	13
10	12
11

어차피 분수의 개수는 각 칸마다 1개니, 순서대로 배열하면 등차수열을 이룬다.

합의 공식. 즉 해당 Group까지의 분수 개수를 알 수 있다.

그러면 N에 1을 대입하여 X가 N보다 작거나 같을 때 까지 반복시키면 된다.

 

N(N + 1) / 2

N = 1,    X = 5
5 <= 1

N = 2,    X = 5
5 <= 3

N = 3,    X = 5
5 <= 6

이렇게 X가 속해있는 Group이 몇 번째 Group인지와 짝수인지 홀수인지도 알 수 있게 된다.

 

자 그럼 이제 이전 그룹까지의 분수 개수를 알면 된다.

각 칸의 분수 개수는 모두 1로 동일하니

공차는 1이다.

 

N_Group까지의 요소 개수 합	N	Group 별 요소
1 3 6 10 15 21	1 2 3 4 5 6	1 1, 2 1, 2, 3 1, 2, 3, 4 1, 2, 3, 4, 5 1, 2, 3, 4, 5, 6

X는 3_Group이니까

속해있는 Group : N = 3

이전 Group       :  N - 1 = 2

이전 Group 까지의 구간합은 3이다.

 

우리는 이제

X가 속해있는 Group의 짝수 홀수 여부

몇 번째 Group인지

이전 Group까지의 분수 개수

들을 알고 있다.

 

1. 3 Group
2. 해당 Group의 분수의 개수는 3
3. 해당 Group은 홀수 Group
4. 이전 Group까지의 분수 개수는 3
5. 해당 Group은 2번과 4번을 인용하여 배열K [ 4, 5, 6 ]란 걸 알 수 있다.

이것이 우리가 알고 있는 정보이다.

해당 Group을 

로 표현하면 N = 3이므로 배열Z [ 1, 2, 3 ]이 된다.

K[] 에서 x의 index = 1;

Z[] 에서 x의 index = 1;

 

이걸 이용하여 분자, 분모를 구할 것이다.

짝수, 홀수 Group에 따라 분모 분자가 증가하는지, 감소하는지 다르니 맞춰서 사용하면 된다.

K[]에서 x의 index를 k라 한다.

증가 : k;

감소 : 해당 Group의 요소 개수 - 1 - k;

이렇게 된다.

 

아래 소스를 첨부한다.

 

import java.io.*;
import java.util.*;

public class Main {
    private static int group, prevGroup;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        List<Integer> arrayByGroup = new ArrayList<>();
        int searchIndex = Integer.parseInt(bf.readLine());
        for (int i = 1; i < searchIndex + 1; i++) {
            arrayByGroup.add(i);
            if (searchIndex <= totalSubByArithmeticSequence(i)) {
                group = i;
                prevGroup = group - 1;
                break;
            }
        }

        int firstValueByGroup = totalSubByArithmeticSequence(prevGroup) + 1;
        int ascSearchIndexByGroup = searchIndex - firstValueByGroup;
        int descSearchIndexByGroup = group - 1 - ascSearchIndexByGroup;

        StringBuilder result = new StringBuilder();
        if (isEvenNumber()) result.append(arrayByGroup.get(ascSearchIndexByGroup))
                .append("/")
                .append(arrayByGroup.get(descSearchIndexByGroup));
        else result.append(arrayByGroup.get(descSearchIndexByGroup))
                .append("/")
                .append(arrayByGroup.get(ascSearchIndexByGroup));

        bw.write(result.toString());
        bw.flush();
        bw.close();
    }

    // 등차수열 합 공식
    private static int totalSubByArithmeticSequence(int index) {
        return index * (index + 1) / 2;
    }

    // 짝수인지
    private static Boolean isEvenNumber() {
        return group % 2 == 0;
    }
}

물론 while 문을 사용하여 구현한다면 더 쉽게 구현할 수 있겠지만,

그렇게 되면 시간 복잡도가 너무 올라가게 되어, 해당 코드처럼 작성하였다.

 

아직은 정리하는 게 서툴어서 내가 제대로 정리한지 모르겠다.

 

후에 읽어보고 이해가 안 된다면 실력 미달이지만,

전달하고자 하는 바가 전달되지 않는다면 수정해야겠다.