[백준] 1193번 : 분수 찾기 - Java

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

1193번: 분수찾기

---

문제

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

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

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

 

입력

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

 

출력

❓풀이 전 이해해야 할 것

• 위 큰 배열의 패턴을 먼저 이해해야 한다.
• 패턴은 파란 선의 움직임대로 짝 수 번째 줄은 위에서 아래로, 홀 수 번째 줄은 아래에서 위로 올라간다.
• 방향이 바뀔 때마다 대각선의 값의 개수가 1개 씩 추가된다. 
• 초록색의 입력 값이 몇 번째 대각선에 위치하는 지, 그 대각선은 짝 수 인 경우와 홀 수 인 경우를 나눠서 연산 해야 한다.

만약 입력 값이 9일 경우?

1+2+3  < 9 < 1+2+3+4 이다.  1+2+3 보다는 크고 1+2+3+4 보다는 작으니 4번째 줄에 위치하게 된다. 

4번째 줄은 짝 수 줄이니 위에서 아래로 내려오게 되고 첫 번째 값은 1/4이다. 

9번 째 수를 구하는 방법은 (4 - (10 - 9)) / (4 + (((10 - 4) - 9) + 1)) 이 된다. (홀 수의 경우 연산을 반대로 진행.)

4번 째 줄, 1+2+3+4를 더한 값인 10, 입력 값인 9이다. 

뒤에 +1을 하는 이유는 배열이나 리스트의 인덱스가 0부터 시작하는 것을 보정하기 위한 것이다.

분수의 위치가 1부터 시작하기 때문에 맞춰서 1을 더해준 것이다.

 

풀이

1. while 반복문으로 X가 어느 대각선에 위치하는 지 찾는다.
   • count는 각 대각선의 마지막 분수까지의 총 분수 개수를 나타낸다.
   • i는 대각선의 순서를 나타낸다.
2. while 문이 종료되면 X가 i번째 대각선에 위치한다는 것을 알 수 있다. 
3. X가 해당 대각선의 마지막 위치로부터 얼마나 떨어져 있는지 계산 한다. (int position = count - X;)
4. X가 해당 대각선의 첫 번째 위치로부터 얼마나 떨어져 있는지 계산한다. (int position2 = (count - i) - X + 1;)
   • +1은 분수의 위치가 1부터 시작하기 때문에 맞춰주기 위해서 1을 더해준다. 
5. 대각선의 순서가 짝수 일 경우 분수의 순서는 오른쪽 위로, 홀수 일 경우는 왼쪽 아래로 출력한다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int X = sc.nextInt();
        int i = 0;
        int count = 0;

        while (count < X) {
            i++;
            count += i;
        }

        int position = count - X; 
        int position2 = (count - i) - X + 1;

        if (i % 2 == 0) {
            System.out.println((i - position) + "/" + (i + position2));
        } else  {
            System.out.println((i+position2 + "/" + (i - position)));
        }
    }
}