백준 JAVA 1193 분수찾기

 

구현을 어떻게 할지 몰라서 블로그를 4개나 찾아봤다

처음에는 2차원배열로 풀어야하나.. 해서 어떻게 하지 했다가 다른 블로그를 찾아보고 코드를 봤는데 이해가 안갔다.

브론즈1 문제인데 혼자생각하고 풀이방법을 이해하는데 50분이걸리다니..

 

조금 낯선문제였다.

일단, 문제에서 주어진 예제에 대해 공식을 이해해야했다. 이게 시간이 많이걸렸다.

 

1그룹 : 1/1

2그룹 : 1/2  2/1

3그룹 : 3/1  2/2  1/3

4그룹 : 1/4  2/3  3/2  4/1

 

순서로보면

1그룹 : 1

2그룹 : 2 3

3그룹 : 4 5 6

4그룹 : 7 8 9 10 

 

먼저, 그룹의 가장 끝 값으로 입력받은값(n) 이 어느 그룹에 속할지 구해야한다. 

1 -> 2 -> 6 -> 10

공식으로 보면 line * (line + 1) / 2 이다.

cnt 가 n보다 작을 때 까지 구해주고 line을 1씩 더해주어 line의 값을 구한다.

---

그룹의 공식을 다시 보면

홀수일 때 -> 분자는 감소되고, 분모는 증가된다.

짝수일 때 -> 분바는 증가되고, 분모는 감소된다.

 

---

 

package BAEKJOON;

import java.util.Scanner;

public class NO1193 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int line = 0; // 어느번째 라인에 있는지 확인
        int cnt = 0;  // 해당 라인의 마지막 수 확인
        int top = 0;  // 분자값
        int bottom = 0; // 분모값

        while (cnt <= n) { // 마지막의 수가 n 보다는 작아야 한다.
            line++;       // 라인수 + 1
            cnt = line * (line + 1) / 2; // 1,3,6,10 ... 배열의 마지막 수 구하기
        }

        if (line % 2 != 0) { // 홀수일때
            top = 1 + cnt - n;
            bottom = line + n - cnt;
        } else {            // 짝수일때
            bottom = 1 + cnt - n;
            top = line + n - cnt;
        }
        System.out.println(top + "/" + bottom);
    }
}