[JAVA]백준 알고리즘 1193번 : 분수찾기

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

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

 

풀이

문제에서 주어진 규칙에 따라 X번째 분수를 찾는 문제이다.

 

표를 자세히 보니, 아래와 같은 규칙을 발견하였다.

 

분모 + 분자 = 2인 분수 : 1개

분모 + 분자 = 3인 분수 : 2개

분모 + 분자 = 4인 분수 : 3개 ...

 

이 규칙에 맞게 위 표를 색으로 구분해 보았다.

 

편의상 1/1을 1번 그룹, 2/1과 1/2를 2번 그룹 ... 으로 표현하겠다.

 

그렇다면 종합적으로 보았을 때, 1번 그룹의 분수의 개수는 1개, 2번 그룹의 분수의 개수는 2개, ... , n번 그룹의 분수의 개수는 n개가 된다.

 

여기서 각 그룹의 분수의 개수가 등차수열을 이루고 있음을 알 수 있다.

 

따라서 등차수열의 합 공식을 이용하면 X를 입력받았을 때 X번째 분수는 몇 번 그룹에 속해있는지 알 수 있다.

아래의 식을 만족하는 가장 작은 n이 X번째 분수가 속해있는 그룹의 번호이다.

 

분모와 분자의 합을 구했다면, 실제 분모와 분자가 무엇인지 출력을 해야 한다.

이것은 X가 몇 번 그룹에 속해있는지 구했다면 어렵지 않게 해결할 수 있다.

위 표를 보면 아래와 같은 규칙을 찾을 수 있을 것이다.

 

1, 3, 5번 그룹과 같이 그룹의 번호가 홀수인 그룹들은 분자가 1부터 1씩 증가한다.

2, 4번 그룹과 같이 그룹의 번호가 짝수인 그룹들은 분모가 1부터 1씩 증가한다.

 

따라서 X번째 분수가 n번 그룹에서 몇 번째에 속해있는지 구하면, 분모와 분자를 찾아낼 수 있다.

필자는 이 역시 등차수열의 합 공식을 이용하여 구했다.

 

X번째 분수는 n번 그룹에 속해있으므로, X에서 1번 그룹부터 n - 1번 그룹까지의 모든 분수의 개수를 빼면 n번 그룹에서 몇 번째 함수인지를 구할 수 있다.

 

n번 그룹의 몇 번째 함수인지 구했다면, 이를 이용하여 해당 분수를 출력하면 된다.

---

🔔 자세한 코드 설명은 더보기 란에 작성하였습니다.

1. X를 입력받고, index와 count를 초기화한다.(group : 그룹 번호, count : 그룹에서 몇 번째 분수인지 구하는 변수)

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

int group = 0;
int count = 0;

 

2. 반복문을 돌려 X가 몇 번째 그룹인지, 그룹에서 몇 번째로 속해있는지 구한다.

for(int i = 1; i <= 4472; i++) {
    if(X <= i * (i + 1) / 2) {
        group = i;
        count = X - (i - 1) * i / 2;
        break;
    }
}

 

3. 그룹의 번호가 홀수이면 분자는 count, 분모는 index - count + 1이다. (분모 + 분자 = 그룹 번호 + 1)

반대로 그룹의 번호가 짝수이면 분모가 count, 분자는 index - count + 1이다.

if(group % 2 == 0) sb.append(count).append("/").append(group - count + 1);
else sb.append(group - count + 1).append("/").append(count);

 

4. 결과를 출력한다. (sb : StringBuilder 클래스 객체)

System.out.println(sb);

---

코드

BufferedReader 클래스와 StringBuilder 클래스를 이용한 코드

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 X = Integer.parseInt(br.readLine());

        int group = 0;
        int count = 0;

        for(int i = 1; i <= 4472; i++) {
            if(X <= i * (i + 1) / 2) {
                group = i;
                count = X - (i - 1) * i / 2;
                break;
            }
        }

        if(group % 2 == 0) sb.append(count).append("/").append(group - count + 1);
        else sb.append(group - count + 1).append("/").append(count);

        System.out.println(sb);
    }
}

틀린 부분이 있다면 정정해 주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!