[백준/JAVA] 🥈 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)가 주어진다.

출력

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

예제 입출력

 

 

 

풀이

첫 번째 대각선까지 값의 개수 = 1

두 번째 대각선까지 값의 개수 = 3

세 번째 대각선까지 값의 개수 = 6 

 

첫 번째 대각선부터 n번째 대각선까지 총 값의 개수를 공식화하면 cnt=n*(n+1)/2;가 되고

아래 코드를 통해 입력된 X가 몇 번째 대각선에 있는지 구할 수 있다.

int n=0; //몇 번째 대각선인지 찾는 코드
int cnt=0;
while(cnt<X){
    n++;
    cnt=n*(n+1)/2;
}

 

 

 

 

대각선의 번호를 찾았다면, 입력된 값이 그 대각선 안에서 몇 번 째에 있는지 정보를 구해야 한다.

X에서 이전 대각선까지의 총 값의 개수를 빼주면 현재 대각선에서 몇 번째 위치의 값인지 알 수 있다

ex) X=5일 때, 5는 3번째 대각선에 위치하고,

5 - (1~2번째 대각선까지 총 값의 개수) = 5 - 3 = 2 => 3번 대각선에서 2번째 값을 가진다.

 

 

최종적으로 정답을 구할 때에는,

빨간 화살표의 위로 올라오는 방향(홀수 값의 대각선 값)

파란 화살표의 아래로 내려가는 방향(짝수 값의 대각선 값)을 나눠서 출력해줘야 함에 유의하자.

 

 

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

public class ex1193_분수찾기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int n=0; //몇 번째 대각선인지 찾는 코드
        int cnt=0;
        while(cnt<X){
            n++;
            cnt=n*(n+1)/2;
        }

        int num = X-(n-1)*n/2;  //대각선에서 몇 번째 위치인지 찾는 코드
        //X-이전 대각선까지의 값의 개수

        int bunja, bunmo;
        if(n%2==0){
            bunja=1; bunmo=n; //1번째 칸에서 세기 시작
            for (int i = 0; i < num-1; i++) { //반복횟수 1감소시켜야 함
                bunja++;
                bunmo--;
            }
        }else{
            bunja=n; bunmo=1;
            for (int i = 0; i < num-1; i++) {
                bunja--;
                bunmo++;
            }
        }
        System.out.println(bunja+"/"+bunmo);
    }
}