백준 [1193 분수찾기]

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다

1/1	1/2	1/3	1/4	1/5	..
2/1	2/2	2/3	2/4	...	...
3/1	3/2	3/3	..	..	...
4/1	4/2	..	...	...
5/1	..	..	...	...
..	..	..	...	...

 

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

---

입력 

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

---

출력

첫째 줄에 분수를 출력한다.

---

문제풀이

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int cnt = 0;
        int n = 0;
        while (true) {
            n++;
            cnt += n;

            if (cnt >= x) {
                if (n % 2 == 0) {
                    System.out.println((x - cnt + n) + "/" + (cnt - x + 1));
                } else {
                    System.out.println((cnt - x + 1) + "/" + (x - cnt + n));
                }
                break;
            }
        }
    }
}

 

지그재그로 나열된  코드들을 자세히 보면 규칙을 찾을 수 있다

대각선이 한 행이라 생각을 해본다면

1번째 행 (1/1)   

2번째 행 (1/2, 2/1)   

3번째 행 (3/1, 2/2, 1/3)   

4번째 행 (1/4, 2/3, 3/2, 4/1) ... 로 이루어진다

 

짝수의 행들은 오 - > 왼 방향으로 순서가 늘어나고 홀수행들은 왼 -> 오 방향으로 순서가 늘어나고 있다.

또한 행의 번호와 분수의 개수가 같은 것을 볼 수 있다..!

int a = in.nextInt(); // 입력받을 분수의 번호
int cnt = 0; // 행에 존재하는 분수의 개수 
int n = 0; // 행의 번호

이 규칙을 바탕으로 위와같이 입력받을 분수의 번호와 분수의 개수와 행의 번호를 저장할 변수를 추가해 준다.

그 후 행(n)이 늘어날 때마다 분수 개수에 행 번호(cnt)를 더해주고 만약 행 번호(cnt)가 a보다 커지면(행에 해당하는 번호의 분수가 있을 경우) 아래 조건식을 거쳐 값을 출력해준다..! 

            if (cnt >= x) {
                if (n % 2 == 0) {
                    System.out.println((x - cnt + n) + "/" + (cnt - x + 1));
                } else {
                    System.out.println((cnt - x + 1) + "/" + (x - cnt + n));
                }
                break;
            }

짝수 행( 오 - > 왼)   분모  : cnt - x + 1,   분자 : x - cnt + n

홀수 행 (왼 -> 오)    분모  : x - cnt + n  분자 : cnt - x + 1