[백준] 1193 분수찾기

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

1193번: 분수찾기

2022-02-06

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main1193 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine().trim());
        int X = Integer.parseInt(st.nextToken());
 
        StringBuilder sb = new StringBuilder();
 
        int T = 1; // 라인
        int base = 1; // 기준 번호
 
        while(true) {
            if(X >= base && X < base+T) {
                // (분모+1)/(분자-1)
                if(T % 2 == 0) { //라인이 짝수 : 기준 번호가 기준부터 오름차순
                    sb.append((1+(X-base))).append("/").append((T-(X-base)));
                    break;
                } else { // 라인이 홀수 : 기준번호 + T 부터 내림차순
                    int tmp = base + T - 1;
                    sb.append(1+(tmp-X)).append("/").append(T-(tmp-X));
                    break;
                }
            } else {
                base += T;
                T++;
            }
        }
 
        System.out.println(sb.toString());
    }
}

#문제풀이

base라는 기준 숫자를 기준으로 대각선 한 줄에 X가 속해져있는지 먼저 찾은 후, 그 범위를 찾으면 짝수/홀수 경우의 수를 나눠서 계산했다.

짝수는 base를 기준으로 홀수는 base+T-1을 기준으로 해당번호를 찾아서 분모, 분자를 찾았다.

 

 

다른 사람 풀이를 보다보니 조금 더 간단한 방법이 있었다.

 

주어진 수 X를 기준으로 num++을 빼면서(각 라인에 있을 수 있는 숫자의 총 갯수) 어떤 라인에 있는지 체크하고 그 라인의 몇 번째인지 바로 계산할 수 있었다.

그리고, 짝수의 경우 위에서부터 카운팅해서 분모가 X, 분자가 (num+1-X)가 되고,

홀수의 경우 아래에서부터 카운팅해서 분자가 (num+1-X), 분모가 X가 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main1193_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine().trim());
        int X = Integer.parseInt(st.nextToken());
 
        StringBuilder sb = new StringBuilder();
 
        int num = 1; // 카운트
 
        while(X > num) {
            X -= num++;
        }
        if(num % 2 == 0) {
            sb.append(X).append("/").append(num+1-X);
        } else {
            sb.append(num+1-X).append("/").append(X);
        }
 
 
        System.out.println(sb.toString());
    }
}