[백준] 1193번: 분수찾기 - java 풀이

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

public class Main {

	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int X = Integer.parseInt(br.readLine());
		
		int i = 1;
		int sum = 0;
		int sum2 = 0;
		int fr = 0; //분수
		int den = 0; //분모		
		
		while(true) {
			sum += i;
			sum2 += i-1;
			if(X<=sum) {
				if(i%2!=0) {
					fr = i - (X-(sum2+1));
					den = 1 + (X-(sum2+1));
					break;
				}else {
					fr = 1 + (X-(sum2+1));
					den = i - (X-(sum2+1));
					break;
				}
			}
			i++;
		}
		System.out.println(fr+"/"+den);
	}
}

 

분수 문제는 어느정도 감을 잡은것 같다

규칙을 찾고 나면 그 이후에는 풀이 방식을 찾는건 간단하다.

 

i (분수 그룹)	X 범위(최대)	X 범위(최소)
1	1	0
2	1+2	1
3	1+2+3	1+2
4	1+2+3+4	1+2+3

 

1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 움직이는데,

홀수 번째 그룹에서는 우상향(3/1 → 2/2 → 1/3)하고, 짝수 번째 그룹에서는 좌하향(1/2 → 2/1)으로 이동하는 걸 알아낼 수 있다. 

 

X의 범위는 굳이 두개 다 생각할 필요없이 최대 또는 최소 범위 하나로 기준을 정하고 풀이를 해주면 된다. 나같은 경우는 X의 범위를 최대를 기준으로 설정하고 막상 분모와 분자를 구할때는 범위를 최소로 정했을 때 더 적합한 방식으로 풀어서 i 일때의 합과 i-1일 때의 합을 따로 구해줬다. 이렇게 풀어도 안되는건 아닌데 짬뽕을 한 덕분에 규칙은 금방 구해놓고 구현을 할 때 좀 헤맸다.

 

if(X<=sum) {
				if(i%2!=0) {
					fr = i - (X-(sum2+1));
					den = 1 + (X-(sum2+1));
					break;
				}else {
					fr = 1 + (X-(sum2+1));
					den = i - (X-(sum2+1));
					break;
				}
			}

 

위에서 i 가 홀수일 때와 짝수일 때 움직이는 방향이 다른걸 고려해서, 분수와 분모를 각각의 경우에 맞게 구분하여 구해준다. 

 

 

규칙은 빠르게 찾았는데 문제를 잘못 읽어서 구현하는데 꽤 오랜 시간이 걸렸다.

그렇다. 비겁한 변명이다.