[백준 1193번/JAVA] 분수찾기

문제

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

1193번: 분수찾기

풀이

아이디어

---

첫 번째 줄 : 1/1
두 번째 줄 : 1/2 -> 2/1
세 번째 줄 : 3/1 -> 2/2 -> 1/3
네 번째 줄 : 1/4 -> 2/3 -> 3/2 -> 4/1
...

 

홀수번째 줄 : (a/b)에서 a는 내림차순, b는 오름차순으로 변한다.
짝수번째 줄 : (a/b)에서 a는 오름차순, b는 내림차순으로 변한다.

---

• X가 몇 번째 줄에 있는 분수인지 구하는 방법:

X-1이 2 이하이면 X는 두 번째 줄에 있다.

X-1-2가 3 이하이면 X는 세 번째 줄에 있다.

...

• X가 3번째 줄에 있다면, 그 줄의 몇 번째 위치에 있는지 구하는 방법:

X-1-2 = K (K<=3)

X는 K번째 위치에 있다. 

---

예)

X=23 번째 분수?
23=(1+2+3+4+5+6)+2 => 7번째 줄 2번째 분수

 

7번째 줄은 홀수이므로 a=내림차순, b=오름차순
2번째 분수이므로 (7/1) (6/2) 따라서 (6/2)가 정답

 

 

알고리즘

X에서 num을 뺀다. (num은 1부터 시작)
num을 1 증가시킨다.

X-num값이 num+1보다 작거나 같다면, num+1번째 줄에 해당된다는 뜻이므로 반복문을 탈출한다.

반복문 탈출 후 X는 X-num, num은 num+1로 업데이트되어있다.
즉 'num번째 줄 X번째 분수'를 구했다.

 

1번째 줄 1번째 분수라면 num=2, X=0일 것이므로 1/1을 출력하도록 한다.

그 외의 경우에는 num이 짝수라면 X-1번 반복하며 a를 오름차순으로, b를 내림차순으로 업데이트한다.
num이 홀수라면  a를 내림차순으로, b를 오름차순으로 업데이트한다.

 

 

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int X = Integer.parseInt(br.readLine());
        int num = 1; //첫번째 줄인지부터 검사
        int a = 1;
        int b = 1;

        //X가 몇 번째 줄 몇 번째 분수인지 구함 (num번째줄, X번째 분수)

        while(true) {
            X-=num; 
            num++;
            if(X<=num) { //X에서 num을 뺀 값이 num+1보다 적다
                break; //반복문 탈출
            }else {
                continue;
            }
        }
        //2번째 줄 2번째 수 = 2/1 num=2, X=2
        if(num==2 && X==0){

        }else if(num%2 == 0) { //짝수번째 줄이면
            b = num;
            for(int i=1; i<X; i++) {
                a++;
                b--;
            }
        }else { //홀수번째 줄이면
            a = num;
            for(int i=1; i<X; i++) {
                a--;
                b++;
            }
        }
        bw.write(a + "/" + b);
        bw.close();
    }
}