백준 1193 분수찾기(Java)

백준 1193

으음.. 저렇게 보면 좀 머리가 아프다

돌리고 돌리고

이미지를 45도 돌려서 피라미드 모양을 만들었다

 

1/1

2/1 <- 1/2

3/1 -> 2/2 -> 1/3

4/1 <- 3/2 <- 2/3 <- 1/4

...

 

지그재그 방향으로 움직임에 주의해야 한다.

짝수 번째 줄은 분자가 커지고 분모가 작아지며,

홀수 번째 줄은 분자가 작아지고 분모가 커진다.

 

https://career-gogimandu.tistory.com/59 에서 등차수열의 합으로 행 마지막 번호를 구한 거 기억해보자.

(방향을 무시하고) 번호로 정리해보면

1

2 3

4 5 6 

7 8 9 10

....

이런식으로 전개가 된다.

그래서 라인 수를 line 이라고 할 때, 각 행 마지막 번호는 line*(line+1)/2 가 된다.

 

 

그리고 저 분수들에서 특이점 하나를 찾을 수 있다.

2+1 = 1+2 = 3, 3 = 2+1

3+1 = 2+2 = 1+3 = 4 , 4= 3+1

4+1 = 3+2 = 2+3 = 1+4 = 5 , 5 = 4 +1

...

 

분자 + 분모 = line + 1 이 된다. ---1)

 

그리고 솔직히 이 다음이 제일 까다로운데, 이것만 이해하면 다 한 거다.

홀수인 3라인에 있는 4번째 분수 3/1 로 예시를 들어보자.

분자 3 = 1 + 3*(3+1)/2 - 4 = 1 + 라인 최종 수 - 내 번호 ---2)

그리고 1) 과 2)를 연립하여

분모 1= line + 1 - 분자 = line + 1 - (1 + 라인 최종 수 - 내번호 ) = line + 내번호 - 라인 최종 수

 

숫자를 좀더 키워서 5라인, 7라인 등으로 테스트해봐도 저 식이 떨어지는 걸 확인한 다음에는

짝수라인의 식을 구하면 되는데

홀수라인에서와 정확히 반대로 하면 된다.

그래서 코드를 다음과 같이 작성했다.

import java.io.*;

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;    //라인수
        int cnt = 0;    //해당라인 마지막수 구할 변수
        int top = 0;    //분자
        int bottom = 0;    //분모
        
        while (cnt < x){
            line ++;    //라인수 +1
            cnt = line * (line+1) / 2;    //1~n라인까지의 합으로 해당라인 최종 수
        }
        
        if(line % 2 != 0){    //홀수 라인
        //분자 + 분모 = 1 + line
            top = 1 + cnt - x;	//분자 = 1 + line*(line+1)/2 - x;
            bottom = line + x - cnt;	//분모 = 1 + line - 분자
        } else {    //짝수 라인
        //홀수라인 케이스와 반대
            bottom = 1 + cnt - x;
            top =  line + x - cnt;            
        }
        
        System.out.println(top + "/" + bottom);
    }
}

분자 + 분모 = 1 + line 까지는 직관적으로 보이는데

그 다음이 조금 까다로워서, 좀 더 이해하기 쉬운 풀이가 있다면 그것도 괜찮을 것 같다는 생각이 든다.