[백준]1193번, 분수 찾기

Q.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.*;
 
public class Prac{
    public static void main(String[] args) {    
        Scanner sc = new Scanner(System.in);
    
        int n = sc.nextInt();//input 입력.
        int cntOfGroup = 0; int sum = 0;
        
        while(sum < n) {//몇번째 그룹에 n번째 원소가 있는지 찾기.
            cntOfGroup++;
            sum += cntOfGroup; 
        }
        int temp = cntOfGroup;
        int A = 1;
        for(int i = (sum-cntOfGroup)+1; i < n; i++) {
            cntOfGroup--;
            A++;
        }
        System.out.println(temp%2 != 0 ? cntOfGroup + "/" + A : A + "/" + cntOfGroup);
    }   
}

<실행 결과>

 

<해 법>

1/1 → 1개

1/2, 2/1 → 2개

3/1, 2/2, 1/3 → 3개

1/4, 2/3, 3/2, 4/1 → 4개

5/1, 4/2, 3/3, 2/4, 1/5 → 5개 

 

각 대각선을 한 그룹으로 치면, 1개, 2개, 3개.... 씩 차례대로 늘어난다.

한 그룹의 분수 갯수는 분자와 분모가 되고, 홀수냐 짝수냐에 따라 분모와 분자의 순서도 달라진다.

 

=>

while(그룹 분자 갯수들의 합 < 입력한 n)

그룹 분수 갯수 += 1

그룹 분수 갯수들의 합 += 그룹 분자 갯수

 

temp = 현재 그룹의 분수 갯수

A = 1 //분자 or 분모가 될 수

 

for(현재 그룹 이전까지의 합부터 n까지)

현재 그룹의 분수 갯수 -= 1

A += 1 

 

if temp가 홀수라면

cntOfGroup + "/" + A

 

else if temp가 짝수라면

A + "/" + cntOfGroup 

 

 

문제 사이트 및 참고 사이트 : https://www.acmicpc.net/problem/1193

※
본 게시물은 개인적인 용도로 작성된 게시물입니다. 이후 포트폴리오로 사용될 정리 자료이니 불펌과 무단도용은 하지 말아주시고 개인 공부 목적으로만 이용해주시기 바랍니다.

※