[BOJ] 1193 분수찾기

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

알고리즘 분류

• 수학
• 구현

알고리즘

문제의 그림에서 왼쪽 아래로 향하는 대각선 level이라고 하고 그 기준으로 볼 때,
오른쪽으로 갈수록 칸 수가 일정하게 증가하고,
각 칸에 속하는 분수들의 분자와 분모의 합은 level+1과 같다는 걸 알 수 있다.

다음은 대각선별로 단을 나눈 그림과 문제의 설명대로 순서를 나타낸 그림이다.

X번째 칸에 오는 분수를 알기 위해서는

• X가 몇 번째 단에 속하는지 : level
• 그 단이 짝수단인지 홀수단인지 : level%2
• 단의 첫번째 칸으로부터 몇 번째 칸에 있는지 : dis

를 알아야 한다.

단에 속하는 칸의 개수는 1, 2, 3, 4, 5, ... 으로 1씩 증가하는 등차수열이고
이걸 이용하여 X가 몇 번째 단에 속하는지 구할 수 있다.

int level = 1; // X가 속한 level
int dis = 0; // level의 첫 번째 칸에서부터의 거리

while(true) { 
       if(X <= (level*(level+1))/2) {
           dis = Math.abs(X - ((level*(level+1))/2));
           break;
      }
      level++;
}

또, level 이 홀수일 때는 칸의 번호가 커질수록 분자가 감소, 분모가 증가하고
level 이 짝수일 때는 칸의 번호가 커질수록 분자가 증가, 분모가 감소한다.
그리고 분자와 분모의 합은 각 level+1 값을 갖는다는 사실을 이용하여 코드를 작성한다.

int t = 0; // 분자
int b = 0; // 분모

if(level%2 == 0) { // 짝수
       t = level - dis;
       b = level + 1 - t;

} else { // 홀수
       b = level - dis;
       t = level + 1 - b;
}

풀이

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

public class baekjoon_1193 {
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {

        int X = Integer.parseInt(br.readLine());
        
        int level = 1;
        int dis = 0;

        while(true) { // X가 속한 level 구하기
            if(X <= (level*(level+1))/2) {
                dis = Math.abs(X - ((level*(level+1))/2));
                break;
            }
            level++;
        }

        int t = 0;
        int b = 0;

        if(level%2 == 0) { // 짝수
            t = level - dis;
            b = level + 1 - t;

        } else { // 홀수
            b = level - dis;
            t = level + 1 - b;
        }

        System.out.println(t + "/" + b);
    }
}