[백준/JAVA] 1193 : 분수찾기 ( 기본 수학 1 )

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

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)가 주어진다.

출력

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

예제 입력	예제 출력
1	1/1
2	1/2
3	2/1
4	3/1
5	2/2
6	1/3
7	1/4
8	2/3
9	3/2
14	2/4

 

 

✅ 다른분의 풀이

import java.io.*;

public class Main{
    public static void main(String[] args)throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        br.close();
        StringBuilder sb = new StringBuilder();
        int crossLine=1;
        int totalCount=0;
        
        while(true){
            if(num<=totalCount+crossLine){
                if(crossLine % 2 == 1){
                    sb.append((crossLine-(num-totalCount-1))).append("/").append(num-totalCount);
                    break;
                } else{
                    sb.append(num-totalCount).append("/").append((crossLine-(num-totalCount-1)));
                    break;
                }
            }else{
                totalCount += crossLine;
                crossLine++;
            }
        }System.out.print(sb.toString());
    }
}

 

✅  계속 생각해봤는데 도저히 어떤공식으로 풀어야할지 감이 안와서 결국 구글링을 했다.

 

1. 대각으로 한칸씩 갈수록 해당 대각선이 갖고있는 칸의 갯수는 1개씩 늘어간다.

    따라서 해당 대각의 칸의갯수를 의미하고있는 crossLine을 1씩 늘려간다.

 

2. totalCount 즉 지금까지의 총 칸의갯수를 누적하는 변수이다.

    

3. 지금까지 누적한 칸과 대각선이 갖고있는 칸의갯수를 더한값이( 지금까지 총 범위의 값이 )

    num보다 작다면 다시 대각을 1칸 옆으로 옮기며 갖고있던값을 totalCount에 누적시킨뒤 1을 증가시킨다.

 

4. 만약 이렇게 반복하다 totalCount + crossLine보다 num이 같거나 작다면

    드디어 해당범위내에 num이 걸린것이다 이제 대각선방향에따라 num이 어디에 위치하는지 찾아주면된다.

 

5. 예제에있던 14로 계산해보자

14 <= 0(totalcount) + 1(crossLine) false
else 0 +=1
        1++; -> 2

14<=1+2;  false
else 1 +=2
         2++; -> 3

14<=3+3  false
else 3+=3
        3++; -> 4

14<= 6+4  false
else 6+=4
        4++; -> 5

14<=10+5  true

여기까지 왔을때 num 14가 범위내에 걸렸다.

이제 분자분모의 순서를 정하기위해 

5 (crossLine) % 2 == 1 true 로 들어간다.

5 - ( 14 - 10 - 1 )  = 2

14 - 10 = 4

 

이렇게 2/4가 나오게된다.

 

 

 

 

사실 보고 또보고 메모장에써가며 봐도 읽을수는있는데 

선뜻 이해가 되지않는다 이제 기본수학1인데. 막막하다

 

 

 

-출처

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

https://st-lab.tistory.com/74