[백준] 1193: 분수찾기

문제

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

1193번: 분수찾기

문제 풀이

https://hoxjeong.tistory.com/51

[백준] 2292: 벌집

이 문제를 푼 후에 풀어서 그런지 2292번을 기반으로 사고를 하게 되었고, 이 문제의 응용 버전이 1193번이라고 느낀다. 

1. 1/1 (1)

2. 2/1 (3) 1/2 (2)

3. 3/1 (4) 2/2 (5) 1/3 (6)

4. 4/1 (10) 3/2 (9) 2/3 (8) 1/4 (7)

실제로 노트에 끄적였던 내용이다. 가장 앞에 인덱스 1,2,3 .. 는 해당 줄의 인덱스이자 이 문제 계차수열의 계차이다. 각 줄의 마지막 인덱스 1,3,4,10 .. 이 계차수열이고, 계차는 공차가 1인 등차수열이다. 공차가 1인 등차수열이라 이 문제에서 각 줄의 인덱스와 계차의 값이 동일하다. 동시에 그 값은 각 줄에 존재하는 분수의 개수이다. 

필요한 변수는 줄의 인덱스(계차, 각 줄의 분수 개수)를 나타내는 변수 i, 각 줄의 마지막 인덱스(계차수열의 값) sum, 각 줄에서 분수를 세는 인덱스 j, 출력할 분자 a, 분모 b이다. 

X > sum 일 때 반복문이 돌아가는데, 다음 sum 값인 sum + i 보다 작거나 같을 때까지 (각 줄의 분수 개수인 i만큼) 각 줄에서 분수 개수를 세며 출력할 값을 정한다. 각 줄에서 분수를 세는 j가 각 줄에서 분수 개수인 i보다 작거나 같을 때까지 반복하되 sum + j가 X-1 일 때까지 반복한다. 그래야 출력할 값이 정확하다.

줄의 인덱스가 홀수일 때와 짝수일 때 분자, 분모가 더해지고 빼지는 방향이 반대이다. 따라서 줄의 인덱스가 홀수인지에 따라 조건을 나누었다.

코드

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

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

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

        int a = 1;
        int b = 1;

        int  i = 1;
        int sum = 1;
        while (X > sum) {
            i += 1;
            int j = 1;
            if (X <= sum+i) {
                if (i % 2 == 1) {
                    a = i;
                    b = 1;
                    while (j <= i && sum+j < X) { // 두 번째 조건 주의. sum + j 가 X-1 일 때 출력할 a,b 완성됨. 
                        a--;
                        b++;
                        j++;
                    }
                } else if (i % 2 == 0) {
                    a = 1;
                    b = i;
                    while (j <= i  && sum+j < X) {
                        a++;
                        b--;
                        j++;
                    }
                }
            }
            sum += i;

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

    }
}