1193_분수 찾기 (JAVA)

1193번: 분수찾기

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();

		int n = 1;
		while(true){
			if(n*(n+1)/2 == X) break;
			else if(n*(n-1)/2<X && n*(n+1)/2>X) break;
            else n++;
		}

		int m = X - n*(n-1)/2; 

		if(n%2==0)
			System.out.println(m+"/"+(n-(m-1)));
		else
			System.out.println((n-(m-1))+"/"+m);
	}
}

 

[문제 풀이 생각 과정]

(1/1) (1/2, 2/1) (3/1, 2/2, 1/3) (1/4, 2/3, 3/2, 4/1) (5/1, 4/2, 3/3, 2/4, 1/5) ... 이런 순서니까

우리는 여기서 ①몇 번째 괄호에 해당하는지, ②괄호 안에서-몇 번째에 해당하는지  를 알아야 한다!

    1) ①몇 번째 괄호에 해당하는지 == n 으로 설정했다.

         위에 쓴 순서들을 번호로 나타내어보면 (1) (2,3) (4,5,6) (7,8,9,10) ... 순서이고,

         괄호 안에서 각 끝자리를 기준으로 살펴보면 1, 3, 6, 10 ... 순으로 나간다.

         이거를 식으로 나타내면 - n*(n+1)/2 이고,  n*(n-1)/2 < X < n*(n+1)/2 를 만족하는 n을 구하면 된다.

      2) ②괄호 안에서- 몇 번째에 해당하는지 == m 으로 설정했다.

           아주 간-단! X - n*(n-1)/2 를 빼면 끝!

      3) 결과는 n이 짝수/홀수 일때로 나누어진다. ( 분자,분모 출력 순서만 바꾸어주면됨! )