[백준] 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(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

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());
        
        
        //분모 분자 합이 홀수면 내려가는 것 

        //1,2,3,4,5
        //1,3,6,10,15
        int sum = 0;
        int cross_count = 1;
        int before_sum = 0;

        while(true){
            before_sum = sum; //0   1   3   6   10
            sum = sum + cross_count; //1,2   3,3     6,4     10,5    15,6

            if (X <= sum){//해당 번째를 알아내야함 --> cross_count알아냄
                int Xth = X - before_sum;
                if (cross_count %2 == 0){ //짝수 --> 아래로
                    System.out.println((Xth)+ "/" + (cross_count+1-Xth));
                    break;
                }
                else{ //홀수  --> 위로  //5  --> 분모 분자 합은 6
                    System.out.println( (cross_count+1-Xth) + "/" + (Xth));
                    break;
                }
            }
            cross_count++; //1, 2      3   4   5 
        }
		br.close();
    }
}

풀이

아웅... 브론즈 수학 문제에도 이렇게 쩔쩔매다니... 문제는 재밌다...

 

그 여기서 포인트는

1. 해당 대각선이 홀수면 아래에서 위로 올라가는 방향/ 짝수면 위애서 아래로 내려가는 방향

2. 분모분자는 대각선에 따라 하나는 증가하고 하나는 감소한다는 것

 

이것들이 포인트이다.

코드는 굉장히 지저분하게 이상한 변수들을 막 여러개 써가면서 코드를 짜서 깔끔하지는 않게 푼거 같다.

 

변수는 총 4가지를 사용했다.

1. X : 입력받는 변수

2. sum : 반복문을 돌면서 어느 대각선에 X번째 값이 존재하는지 파악하기 위한 변수이다. 

  - X가 만약에 14라면 sum은 1,3,6,10,15 이렇게 증가하면서 5번째 반복문을 돌때 5번째 대각선에 머문다는 것을 알 수 있다.

3. before_sum : X가 해당 대각선에서 몇번째에 존재하는지 알기위해 만든 변수다.

  - X- before_sum을 하면 X가 해당대각선에서 4번째에 위치하는지 알 수 있다. 

4. before_count : 몇 번째 대각선에 X가 존재하는지 파악하는 변수, 분모 분자의 최대값은 before_count를 넘지 않는다 따라서 출력을 할 때도 해당 변수를 사용해서 출력을 했다.