[백준/Java]Q1193

백준 알고리즘 8단계 기본 수학1 1193번 문제입니다.

---

Q. 무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

그림 출처 : https://www.acmicpc.net/problem/1193

[입력]

- 정수 X가 주어진다.

[조건]
- X(1 ≤ X ≤ 10,000,000)

  Ex) 14 -> 2/4

 

풀이

조건을 생각했을 때, 배열의 분수들은 다음과 같이 규칙을 가지고 있었다.

1/1부터 1이 시작된다.

 

2~3은 순서대로 1/2, 2/1 분자가 1씩 증가(2까지)하고 분모는 1씩 감소(2부터)한다. (2~3 개수 : 2)

4~6은 순서대로 3/1, 2/2, 1/3 분자가 1씩 감소(3부터)하고 분모는 1씩 증가(3까지)한다. (4~6 개수 : 3)

7~10은 순서대로 1/4, 2/3, 3/2, 4/1 분자가 1씩 증가(4까지)하고 분모는 1씩 감소(4부터)한다. (7~10 개수 : 4)

11~15는 순서대로 5/1, 4/2, 3/3, 2/4, 1,5 분자가 1씩 감소(5부터)하고 분모는 1씩 증가(5까지)한다. (11~15 개수 : 5)

 

찾은 규칙대로 답을 얻기 위해 먼저, 입력받은 숫자 X의 범위를 탐색했다.

그리고 범위 내에서 X의 위치를 구했고 해당 범위의 개수(Ex. 4~6 : 3)가 짝수인지 홀수인지 체크해 증가/감소 처리를 했다.

 

소스

package com.baek.algo;

import java.util.Scanner;

public class Q1193 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int x = sc.nextInt();
		int i = 1;
		String result = "";

		if(x == 1) {
			result = "1/1";
		} else {
			int min = 1;
			int max = 1;

			while(true) {
				min = min + i;
				max = max + (i + 1);

				if(x >= min && x <= max) {
					int pos = 0;

					for(int k = min; k <= max; k++) {
						if(x == k) {
							break;
						}
						pos = pos + 1;
					}

					int cnt = max - min;
					int a = 0;
					int b = 0;

					for(int j = 0; j <= cnt; j++) {
						if(j == pos) {
							if(cnt % 2 == 0) {
								a = (cnt + 1) + (j * -1);
								b = j + 1;
							} else {
								a = j + 1;
								b = (cnt + 1) + (j * -1);
							}
						}
					}
					result = a + "/" + b;
					break;
				}

				i = i + 1;
			}
		}

		System.out.println(result);

		sc.close();
	}
}