백준/1193번 :: 분수 찾기 (Java 자바 구현) 알고리즘 풀이

 

※ 문제 풀이 코드는 맨 아래에 있습니다.

 

문제

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

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)가 주어진다.

 

출력

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

 

예제입력

14

 

예제출력

2/4

 

코드

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

public class Ex1193 {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int line = 0;
        int cnt = 0;
        while(cnt < n) {
            line++;
            cnt = line * (line+1) / 2;
        }
        
        if( line % 2 != 0) {
            int top = 1+(cnt-n);
            int bottom = line - (cnt-n);
            System.out.println(top+"/"+bottom);
        }else {
            int top = line - (cnt - n);
            int bottom = 1 + (cnt - n);
            System.out.println(top+"/"+bottom);
        }// end if
        
    }
}​

 

표의 대각선을 봤을때, 각 줄의 항의 개수는 등차수열을 이룬다.

1/1

2/1, 1/2

3/1, 2/2, 1/3

...생략...

따라서, 중학교 때 배우는 등차수열의 법칙 n(n+1)/2 (n : n번째 까지 항의 개수) 을 이용해서 몇번째 줄에 위치한 항의 개수인지 판단한다.

 

 

짝수번째 줄일때와 홀수번째 줄일때 반대 방향을 가지므로, 마지막 조건문을 이용해서 홀수와 짝수일때 다른 결과를 나타나게 해준다.

 

결과

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

문제 출처

https://www.acmicpc.net/problem/1193