[백준] 1193번 - 분수찾기 (JAVA)

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

1193번: 분수찾기

 

- 문제 -

---

- 풀이 과정 -

T = 분모, 분자의 합

cur = 각 대각선 당 원소의 개수

prev_sum = 이전 대각선 원소 개수의 합

 

주어진 분수에서 규칙을 찾아보면 각 대각선 별 분모, 분자의 합이 T와 같습니다.

또한 대각선의 원소의 개수가 하나씩 증가하는 것을 볼 수 있습니다.

여기서 문제는 X번째의 분수를 찾아야 하는데 순서가 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> …. 순으로 진행됩니다.

현재 원소의 개수가 홀수면 ↗방향으로 진행이 되고 원소의 개수가 짝수면 ↙방향으로 진행이 됩니다.

진행 방향에 따라 ↙방향은 분자가 증가하고 ↗방향은 분모가 증가하는 형태를 볼 수 있습니다.

 

X번째 분수를 찾기 위해 대각선 위치를 증가(cur++)되는데 이전 대각선의 원소 개수를 합(prev_sum)해 줍니다.

만약 X가 14인 경우 원소의 개수가 14보다 큰 경우를 찾기 위해 순서대로 가다 보면 대각선의 위치가 증가됩니다.

 

그러면 X의 위치는 cur =5 대각선의 위치가 되며 이 때 prev_sum=10이 됩니다. 해당 대각선에서 X의 위치를 찾기 위해 X(14) – prev_sum(10)을 하게 되면 대각선의 4번째 위치한 분수가 됩니다.

 

이 때 대각선의 원소 개수가 짝수인지 홀수인지 판별하여 X번째 수를 분자로 셀지 분모로 셀지 결정합니다.

 

X번째 수가 분모로 결정되었다면 나머지 분자는 [현재 원소의 개수 값(cur)+1]=T에서 분모 값(x-prev_sum)을 뺀 값으로 분자 값을 구해줄 수 있습니다.

---

- 소스 코드 -

import java.util.Scanner;
 
public class Main {
    //1193번
    public static void main(String[] args) {    
        Scanner sc = new Scanner(System.in);
        int x=sc.nextInt();    // 몇 번째 위치 값
        int prev_sum=0, cur=1;    // 이전 원소 개수의 합, 현재 원소 개수
        while(true) {
            if(x<=prev_sum+cur) {    //이전+현재 원소 개수가 입력 값보다 큰 경우
                if(cur%2==1) {
                    System.out.println((cur+1-(x-prev_sum))+"/"+(x-prev_sum));
                    break;
                }else {
                    System.out.println((x-prev_sum)+"/"+(cur+1-(x-prev_sum)));
                    break;
                }
            }else {    //이전+현재 원소 개수가 입력 값보다 작은 경우
                prev_sum+=cur;    // 이전 원소 합 + 현재 원소 개수
                cur++;    // 현재 원소 개수 증가
            }
        }
    }    
}