[Silver V][JAVA] 11393번:분수찾기

알고리즘

분수찾기: 11393번
분류: 수학 구현

분모 값과 분자 값의 합을 T 라고 할 때 다음과 같은 규칙이 생긴다.

그리고 대각선 칸의 개수는 T - 1 개다.
파란색 ( T 가 짝수, 또는 대각선 칸의 개수가 홀수 ) 일 때는 왼쪽 아래에서 오른쪽 위 방향 ( ↗︎ ) 으로 진행되고,
빨간색 ( T 가 홀수, 또는 대각선 칸의 개수가 짝수 ) 일 때는 오른쪽 위에서 왼쪽 아래 방향 ( ↙︎ ) 으로 진행된다.
즉, T % 2 가 0 일 때는 대각선 위 방향, 1 일 때는 아래 방향으로 진행된다.

홀수 그룹은 분자가 감소하고 분모가 증가한다.
짝수 그룹은 분자가 증가하고 분모가 감소한다.

이용할 변수:

입력받을 X 값
해당 범위의 대각선 칸 개수 ( cross_count )
해당 대각선 직전 대각선 까지의 칸의 누적 합 ( prev_count_sum )

이렇게 3 개를 이용하여 X 값이 해당 범위의 값이 나올 때 까지 반복하고,만약 해당 범위의 값이라면 대각선의 개수가 홀수인지, 짝수인지 판별하여 해당 대각선의 첫 원소와 X, 대각선의 개수를 이용하여 분모 분자 값을 구해준다.

전체소스

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

public class 분수찾기 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine());

        int cross_count = 1, prev_count_sum = 0;

        while (true) {
            // 직전 대각선 누적합 + 해당 대각선 개수 이용한 범위 판별
            if (X <= prev_count_sum + cross_count) {

                if (cross_count % 2 == 1) {	// 대각선의 개수가 홀수라면
                    // 분자가 큰 수부터 시작
                    // 분자는 대각선상 블럭의 개수 - (X 번째 - 직전 대각선까지의 블럭 개수 - 1)
                    // 분모는 X 번째 - 직전 대각선까지의 블럭 개수
                    System.out.print((cross_count - (X - prev_count_sum - 1)) + "/" + (X - prev_count_sum));
                    break;
                }

                else {	// 대각선의 개수가 짝수라면
                    // 홀수일 때의 출력을 반대로
                    System.out.print((X - prev_count_sum) + "/" + (cross_count - (X - prev_count_sum - 1)));
                    break;
                }

            } else {
                prev_count_sum += cross_count;
                cross_count++;
            }
        }
    }
}