[백준] 1193 분수찾기 - Java

문제

링크

---

코드

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

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());
        br.close();

        int layer = 1;
        int count = 0;
        int top, bottom;
        while (true) {
            if (X <= layer + count) break;
            count += layer;
            layer++;
        }

        int index = X - count;
        if (layer % 2 == 1) {
            top = layer - (index - 1);
            bottom = index;
        } else {
            top = index;
            bottom = layer - (index - 1);
        }
        System.out.println(top + "/" + bottom);
    }
}

---

리뷰

개인적으로 식을 구성하는데 되게 오래걸렸던 문제이다 😱
분수가 지그재그로 번호가 정해진다.

대각선으로 기울여 생각해보면

	1/1						1
  2/1 1/2				   3 2
 3/1 2/2 1/3			  4 5 6
4/1 3/2 2/3 1/4          10 9 8 7

형태를 띄고 다음과 같은 규칙을 가진다.

1. 각 행(layer)의 분자와 분모의 합은 layer + 1이다.
2. 각 행의 분자 또는 분모의 최댓값은 layer와 같다.
3. 행이 홀수이면 순서대로 분자는 감소하고 분모는 증가한다.
   행이 짝수이면 순서대로 분자는 증가하고 분모는 감소한다.
4. 행의 홀수/짝수 여부에 따라 분모와 분자를 반대로해주면 된다.
   
   

X번에 해당하는 분수를 찾기위해 필요한것은
몇 번 행인지, 그 행의 몇 번째 숫자인지이다.

int layer = 1;
        int count = 0;
        int top, bottom;
        while (true) {
            if (X <= layer + count) break;
            count += layer;
            layer++;
        }

예를 들어 5번의 분수를 구한다고 해보자
while문을 통해 3번째 행에 5번이 있음을 알 수 있다.
count를 통해 직전의 행은 3번에서 끝나는 것을 알 수 있으니 이를 통해
몇 번 행인지 -> 3번 행
그 행의 몇 번째 숫자인지 -> X - count -> 2번째 숫자를 구할 수 있다.

if (layer % 2 == 1) {
            top = layer - (index - 1);
            bottom = index;
        } else {
            top = index;
            bottom = layer - (index - 1);
        }

이 식을 구하는게 많이 헷갈렸는데

행이 홀수이므로 순서대로 분자는 감소하고 분모는 증가한다. (3번 규칙)

분자가 최대값에서 시작하니까 첫번째 숫자는 3 두번째는 2 세번째는 1이되어야한다.
첫번째 숫자일 경우 최대값이여야하므로 layer - (index - 1)로 표현하였다.
분모는 최솟값에서 시작하니까 index 값을 그대로주면 된다.

짝수일 경우 이와 반대이므로 위치만 바꾸어주었다. (4번 규칙)

뭔가 느낌은 알겠는데 식이 설명할 수 있는 느낌이 바로오지않아 풀었는데도 개운하지가 않다 😅
(지금까지 풀었던 실버문제보다 어려운거같은데 구현자체는 쉬워서 점수가 낮은듯하다)