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번째 분수를 구하는 프로그램을 작성하시오.

입출력

1. 입력

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

2. 출력

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

예제

입력	출력
1	1/1
2	1/2
3	2/1
4	3/1
5	2/2
6	1/3
7	1/4
8	2/3
9	3/2
14	2/4

풀이

문제를 보고 하루 동안 고민을 해도 못 풀어서 구글에 답을 검색했지만 완벽하게 이해하지 못했다.
우선 풀이를 하자면

 

탐색 과정

표를 보기 쉽게 그리면 위 사진처럼 볼 수 있다. 여기서 찾을 수 있는 특징은 짝수행 일 경우 분자가 오름차순이고, 홀 수행 일 경우 분자가 내림차순인 것을 알 수 있다.
따라서 내림차순일 때의 공식과 오름차순 일 때의 공식을 구하면 주어진 위치의 분수를 구할 수 있다.

차순별 공식

sum을 각 행별 숫자의 총 개수, floor는 행(층), inputNumber를 입력값이라 했을 때, 수가 내림차순 일 경우
수를 나열해보면 각 행별 숫자의 총 개수(sum)에서 입력값(inputNumber)을 뺀 값에 1을 더해준 값이 분자(분모) 임을 알 수 있다.
위 공식이 유도되는 이유는 각 행별 숫자의 총개수에서 입력된 값이 얼마나 떨어져 있는지 를 물어보고 있기 때문이다.

내림차순 일 경우

반대로 수가 오름차순 일 때 나열하면, 행(floor)에서 총 개수(sum)를 뺀 값에 inputNumber을 더해준 값이 분자(분모) 임을 알 수 있다.

오름차순 일 경우

따라서 위 두 식을 정리하면 이런 공식을 도출할 수 있다. 홀 수행일 때 [내림차순 공식 / 오름차순 공식], 짝수행일 때 [오름차순 공식 / 내림차순 공식]을 해주면 된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int inputNumber = scan.nextInt();
        int sum = 0;    //각 층의 합
        int floor = 0;  //층

        while(true){
            floor++;    //층 증가
            sum+=floor; //숫자의 총 갯수

            //입력값의 층에 도착했을 때
            if (sum >= inputNumber) {
                //짝수행
                if (floor % 2 == 0) {
                    System.out.println((floor - sum + inputNumber) + "/" + (sum - inputNumber + 1));
                }
                //홀수행
                else {
                    System.out.println((sum - inputNumber + 1) + "/" + (floor - sum + inputNumber));
                }
                break;
            }
        }
    }
}

kotlin code

import java.util.*

fun main() {
    val scan = Scanner(System.`in`)
    val inputNumber = scan.nextInt()
    var sum=0     //각 층의 합
    var floor=0   //층

    while (true){
        floor++     //층 증가
        sum+=floor  //숫자의 총 갯수

        //입력값의 층에 도착했을 때
        if(sum>=inputNumber){
            //짝수행
            if(floor%2==0){
                print("${floor-sum+inputNumber}/${sum-inputNumber+1}")
            }
            //홀수행
            else{
                print("${sum-inputNumber+1}/${floor-sum+inputNumber}")
            }
            break;
        }
    }
}