[백준 알고리즘] 1193번 분수찾기 Java

분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 -> ... 과 같이 지그재그 순서로 차례대로 1~..번 분수라고 한다.

 x가 주어졌을 때 x번째 분수를 구하란다.

일단 저 표대로 보려니까 너무 어려워서 그림을 돌려봤다.

피라미드처럼 본다고 그리고 볼 수 있다고 생각하자.

첫번째 라인은      1/1

두번째 라인은   2/1 1/2

세번째 라인은 3/1 2/2 1/3

...

순서는   1

          3 2 

         4 5 6 .. 이다

여기서 발견한 규칙은

짝수 행은 오른쪽에서 왼쪽, 홀수 행은 왼쪽에서 오른쪽으로 순서가 커지고

행 번호 + 1 = 분모 + 분자,

행의 번호와 그 행의 분수의 숫자는 같다.

a : 원하는 분수 번호

cnt : 개수

n : 행 번호

n에 1씩 더할 때 마다 cnt에 n을 더하고 만약 cnt가 a보다 커질 경우(그 행에 원하는 번호 분수가 있을 경우)

짝수 행이라면 오른쪽에서 왼쪽으로 가니 분모는 cnt - a + 1 분자는 a - cnt + n

홀수 행이라면 왼쪽에서 오른쪽으로 가니 분모와 분자를 반대로 주면 된다. 코드는

import java.util.Scanner;
public class back1193 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int cnt = 0;
		int n = 0;
		while (true) {
			n++;
			cnt +=n;
			if(cnt>=a) {
				if(n%2==0) {
					System.out.println(a-cnt+n+"/"+(cnt-a+1));
				}else {
					System.out.println((cnt-a+1)+"/"+(a-cnt+n));
				}
				break;
			}
		}
	}
}

이렇게 작성하였다.