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

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

1193번: 분수찾기

 

 

 

 

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));
        int x = Integer.parseInt(br.readLine());
        int line = 0; // 몇 번째 줄인지
        while(line * (line + 1)/2 < x){
            line++;
            /*
                line * (line + 1) / 2 = 등차
                ex. 첫 번째 라인에 올 수 있는 가장 큰 수 : 1 = (1 * (1 + 1) / 2)
                    두 번째 라인에 올 수 있는 가장 큰 수 : 3 = (2 * (2 + 1) / 2)
                    세 번째 라인에 올 수 있는 가장 큰 수 : 6 = (3 * (3 + 1) / 2)
                    네 번째 라인에 올 수 있는 가장 큰 수 : 10 = (4 * (4 + 1) / 2)
                    다섯 번째 라인에 올 수 있는 가장 큰 수 : 15 = (5 * (5 + 1) / 2)

                    각 라인에 올 수 있는 가장 큰 수는 각각 이전 라인에 올 수 있는 가장 큰 수보다 1, 2, 3, 4, 5씩 증가하므로 등차수열이 성립한다.
                    ==> line번 째 라인에 올 수 있는 가장 큰 수(max라고 가정) = line * (line + 1) / 2 이므로
                        입력받은 K가 max 값보다 작을 경우 그 라인에 존재함을 알 수 있다.
                        ex. K = 13, max = 10(4번 째 라인의 max값) ==> 4번 째 라인에 올 수 있는 가장 큰 값이 10인데 주어진 값은 13이므로 탈락! (max < x)
                        ex. K = 13, max = 15(5번 째 라인의 max값) ==> 5번 째 라인에 올 수 있는 가장 큰 값이 15인데 주어진 값은 13이므로 해당 라인에 포함 가능! (max >= x)
                        
                    ===> 그렇기 때문에 몇 라인에 주어진 값 x가 들어갈 수 있는지를 찾는다.
            */
        }

        int prev = (line - 1) * line / 2; // 위에서 찾은 line 번째 라인의 바로 전 라인에 올 수 있는 최댓값을 구한다. ex. line이 5라고 한다면 4번째 라인에 올 수 있는 최댓값(10이 됨) 
        // prev는 원래 ((line - 1) * ((line - 1) + 1) / 2)인데 이를 정리하면 (line - 1) * line / 2가 됨
        
        /*
            ! 그림에서 볼 수 있듯이 홀수 라인은 아래서 위로, 짝수 라인은 위에서 아래로 진행하므로 라인이 짝수냐 홀수냐에 따라 값이 달라진다. !
            
            ** 여기서 알아두어야 할 점
            1. 해당 라인에 있는 모든 분수들의 분자 + 분모 값은 line + 1이다. 
                ex. 3라인에 있는 분수들은 각각 3/1(분자 + 분모 = 4), 2/2(분자 + 분모 = 4), 1/3(분자 + 분모 = 4)으로 모든 분자 + 분모의 값이 3(해당 라인)+1인 4가 된다.)
            2. 라인이 짝수인 경우(위 -> 아래로 진행)
                2-1. 분자 값은 위에서 아래로 내려갈 수록 오름차순 ex. 4번 째 라인의 분자 값들은 각각 1,2,3,4
                2-2. 분모 값은 위에서 아래로 내려갈 수록 내림차순 ex. 4번 째 라인의 분모 값들은 각각 4,3,2,1(위 -> 아래)
            3. 라인이 홀수인 경우(아래 -> 위로 진행)
                3-1. 분자 값은 아래에서 위로 올라갈 수록 내림차순 ex. 3번 째 라인의 분자 값들은 각각 3,2,1(아래 -> 위)
                3-2. 분모 값은 아래에서 위로 올라갈 수록 오름차순 ex. 3번 째 라인의 분모 값들은 각각 1,2,3(아래 -> 위)
        */

        // top: 분자 값, bottom: 분모 값
        if(line % 2 == 0){ // 라인이 짝수라면
            // line은 4, x는 9라고 가정. 9에 해당하는 분수는 3/2
            // prev값은 (4-1)*4/2 = 6이므로 3라인(4라인의 바로 이전라인)의 최댓값은 6이 된다.
            int top = x - prev; // 9에 해당하는 값의 분모는 3임 = x(주어진 값) - prev(이전 라인의 최댓값) = 9 - 6에 해당하는 값.
            int bottom = line + 1 - top; // 위에서 모든 분수의 분자 + 분모값은 line + 1이라고 했으므로 (top + bottom = line + 1) == (botton = line + 1 - top)
            System.out.println(top + "/" + bottom);
        } else { // 라인이 홀수라면
            // line은 5, x는 14라고 가정. 14에 해당하는 분수는 2/4
            // prev값은 (5-1)+5/2 = 10이므로 4라인(5라인의 바로 이전라인)의 최댓값은 10이 된다.
            int bottom = x - prev; // 14에 해당하는 값의 분모는 4임 = x(주어진 값) - prev(이전 라인의 최댓값) = 14 - 10에 해당하는 값
            int top = line + 1 - (bottom); // 위에서 모든 분수의 분자 + 분모값은 line + 1이라고 했으므로 (top + bottom = line + 1) == (botton = line + 1 - top)
            System.out.println(top + "/" + bottom);
        }

    }
}