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

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

이해만 하면 코드 자체는 간단한데 이해하기가 상당히 어려운 문제였다. 처음에는 순서를 잘못 이해했었는데, 진행방향은 아래와 같다.

대각선 왼쪽 위부터 홀수번째 라인은 ↗ 방향으로 나아가고 짝수번째 라인은 ↙ 방향으로 나아가는 지그재그 순서이다. 분수는 1+2+3+4+5+... 순서로 증가하고, 무한히 큰 배열이므로 증가량이 감소하진 않을 것이다.

따라서 x가 n번째 라인에 존재할 때, $x=\displaystyle\sum_{k=1}^{n} k$, 즉 $x=n(n-1)/2$이다. 아래 코드에선 for문을 통해 n을 구하였다. 정확히 나누어지진 않을 수도 있기 때문에 (n-1)일 때의 값과 n일 때의 값 사이의 범위이기만 하면 break로 멈춘다.

int num = x-n*(n-1)/2는 x번째 분수가 n번째 라인의 몇번째 순서에 존재하는지를 뜻한다. x에서 x 이전 줄까지의 값을 뺀 나머지를 구하여 한 라인에서의 순서를 알아낼 수 있다.

짝수번째 라인에 존재하는지, 홀수번째 라인에 존재하는지에 따라 분모/분자가 반전된다. 표의 대각선 가운데는 n/n이라는 점에 유의한다.

소스코드

---

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
        BufferedReader br = 
        		new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());
        
        /*
         * 1+2+3+4+5+... 순으로 수가 증가한다.
         * 이때 x = n(n+1)/2로 두고 n을 구하면 x가 몇번째 라인에 존재하는지 알 수 있다.
         * x가 n번째 라인에 존재할 때
         * 짝수번째 라인은 ↙ 방향이고 홀수번째 라인은 ↗ 방향임에 유의한다.
         */
        int n;
        for(n=1; ; n++) {
        	if((n-1)*n/2 <= x && x <= n*(n+1)/2)
        		break;
        }
        
        /*
         * 대각선 가운데는 n/n 형식
         * 이때 num은 한 줄에서 몇번째 순서에 존재하는지이다. (전체 x에서 이전 줄의 값을 뺀 숫자)
         */
        int num = x-n*(n-1)/2;
        if (n%2 == 0)
        	System.out.println(num+"/"+(n-num+1));
        else
        	System.out.println((n-num+1)+"/"+num);
	}
}