[백준 알고리즘][자바] 1193번 : 분수찾기

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

1193번: 분수찾기

이번 포스팅은 백준 알고리즘 1193번 : 분수 찾기입니다.

분수의 순서를 위의 번호로 하고 X가 주어졌을 때, X번째 분수가 무엇인지 구하는 문제입니다.

분수의 규칙성을 생각하다 보면 어렵지 않게 파악할 수 있습니다.

1/1을 기준으로 1층이라고 한다면 각 층의 시작점인 분수에서

홀수 층에서는 분자는 1씩 줄어들고 분모는 1씩 늘어납니다.

짝수 층에서는 분자는 1씩 늘어나고 분모는 1씩 줄어듭니다.

 

이런 규칙을 기준으로 코딩을 짜게 됩니다.

저 같은 경우에는 아래의 두 가지의 개념으로 코드를 짰습니다.

1. 주어진 숫자 X의 층 수
2. 주어진 숫자 X는 해당 층의 시작점인 분수를 첫 번째 방이라고 했을 때, 몇 번째 방에 위치하는 가?

몇번째 방에 위치하는 지를 구할 수 있으면, 분자 분모가 얼마나 줄어들었는지 구할 수 있습니다.

가령 X가 9라고 한다면

9는 4층에 위치해있고 3번째 방에 위치해있으므로

분수는  (방의 위치) / 층수 - (방의 위치 - 1)의 공식으로 구할 수 있습니다. 따라서 3/2가 되는 것이죠.

저의 방식이 일반적이지는 않습니다. 다른 사람들이 푼 방식도 참고해보세요.

 

층 수를 구하는 방법은 층수를 늘려가며 각 층의 분수들의 개수의 합이 이 주어진 숫자 X를 넘을 때가 해당 층이 됩니다.

 

방의 위치를 구하는 방법은 층을 구했으면 주어진 숫자 X에서 직전의 층의 분수들의 갯수의 합을 빼면 됩니다.

 

분수들의 갯수의 합은 가우스 방식을 사용합니다.

1부터 N 까지의 합 = N * (N + 1) / 2

1 부터 N -1까지의 합 = (N - 1) * N / 2

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int X = Integer.parseInt(br.readLine()); // 주어진 숫자 X
		int floor = 1; // 주어진 숫자 X가 위치한 층 수
		int room = 1; // 주어진 숫자 X가 위치한 방의 위치(몇번째 인가?)
		while (true) { // 층 수 구하기
			if (X <= (floor * (floor + 1)) / 2) { // 분수 갯수의 합이 X를 넘을 때가 층의 위치
				room = X - (floor * (floor - 1)) / 2; // 방의 위치 구하기
				break; // 루프 빠져 나옴
			} else { // 아니면
				floor++; // 층 수 늘리기
			}
		}
		
		if(floor % 2 == 0) { // 층의 위치가 짝수일 때
			bw.write(room + "/" + (floor - (room - 1)));
		}else { // 층의 위치가 홀수일 때
			bw.write((floor - (room - 1)) + "/" + room);	
		}

		br.close();
		bw.flush();
		bw.close();
	}
}

헷갈리는 부분을 댓글을 남겨주세요 :)

감사합니다.