문제 번호 1193번 : 분수찾기 - JAVA [자바]

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

1193번: 분수찾기

 

이 문제도 수열에 관한 문제입니다. 규칙을 알면 쉽게 문제를 풀 수 있습니다.

숫자를 나열하면

1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 3/1 -> 1/4 -> 2/3 -> 3/2 -> 4/1 -> 5/1 -> 4/2 -> 3/3 -> 2/4 -> 1/5 ...

위에 같은 형태를 나타내게 됩니다. 가만히 보게 되면 규칙성이 보이게 됩니다. 

 

(1/1) -> (1/2 -> 2/1) -> (3/1 -> 2/2 -> 3/1) -> (1/4 -> 2/3 -> 3/2 -> 4/1) -> (5/1 -> 4/2 -> 3/3 -> 2/4 -> 1/5) -> ...

 

괄호를 친 기준을 보시면 분자와 분모의 최댓값을 기준으로 묶었습니다. 첫 번째 괄호의 최댓값은 1이고 두 번째 괄호의 최댓값은 2이고 세 번째 괄호의 최댓값은 3입니다. 그리고 짝수 번째와 홀수 번째의 괄호의 분모, 분자의 증가 감소 값이 동일합니다. 짝수 번째는 분수가 1부터 늘어나고 분모는 최댓값에서 1씩 줄어듭니다. 홀수 번째는 반대로 분자가 최댓값에서 1씩 줄어들고 분모가 1부터 1씩 늘어납니다.

 

1193번 : 분자 찾기의 문제의 의미는 수열이 몇 번째인지 알려줄 테니 그 수열의 분수 값을 출력하라는 의미입니다.

즉, 해당 수열의 번호가 어디 괄호에 속해 있는지 알고 그 괄호의 몇 번째인지 알면 분수 값을 알 수 있습니다. 

좀 더 이해를 위해 아래 정답 코드를 보겠습니다.

 

정답

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
		
		int x = sc.nextInt();
		int count = 0;
		int i = 1;
		int deno = 0;
		int numer = 0;
		while(count < x) {
			count = count + i;
			i++;
		}
        
		if((i-1)%2 == 0) {
			deno = 1 + (count - x);
			numer = (i-1) - (count-x);
		}else {
			deno = (i-1) - (count-x);
			numer = 1 + (count - x);
		}
		
		
		System.out.println(numer  + "/" + deno);
    }
}

 

먼저 각 변수 선언의 의미를 설명하겠습니다. 

x로 몇 번째 수열을 구하는지 입력받습니다.

count와 i는 몇 번째 괄호인지 알아내기 위한 변수입니다. 밑에서 저 자세히 설명하겠습니다.

deno는 출력할 분모입니다.

numer는 출력할 분자입니다.

int x = sc.nextInt();
int count = 0;
int i = 1;
int deno = 0;
int numer = 0;

 

밑에 코드를 이해하려면 먼저 수열을 어떻게 해석했는지 이해해야 합니다.

(1/1) -> (1/2 -> 2/1) -> (3/1 -> 2/2 -> 3/1) -> (1/4 -> 2/3 -> 3/2 -> 4/1) -> (5/1 -> 4/2 -> 3/3 -> 2/4 -> 1/5) -> ...

위에 수열을 보시면 해당 개수와 최댓값이 동일합니다.

즉, 1번째 괄호는 최댓값이 1이고 개수도 1개입니다. 두 번째 괄호는 최댓값이 2이고 개수도 2개입니다. 3번째 괄호는 최댓값이 3이고 개수도 3개입니다. 이렇게 개수가 늘어남에 따라 규칙 안에 있는 괄호의 순서도 늘어나게 됩니다. 각 괄호의 마지막 수열은 다음 과 같이 늘어납니다.

1 -> 3(1+2) -> 6(3+3) -> 10(6+4) -> 15(10+5)...

위 수열이 이해가 안될 수 있는데 

1->3->6->10->15..가 뜻하는 건 괄호의 마지막 수열에 순번입니다.

즉 1은 첫 번째 괄호의 마지막 순번 1번 수열을 의미하고요

3은 두 번째 괄호의 마지막 순번 2/1이 3번째 수열임을 의하고요

6은 세 번째 괄호의 마지막 순번 3/1이 6번쨰 수열임을 의미힙니다.

규칙을 보시면 앞의 수에다가 해당 괄호의 번호를 더해주면 됩니다. 

즉, 앞의 마지막 수열 + 괄호 번호를 해주면 다음 괄호의 마지막 번호가 나오게 됩니다. 

다음 코드는 앞의 수열에 괄호 번호를 더해서 count가 괄호의 마지막 수열을 찾아낼 수 있는 코드입니다.

while 문으로 해당 입력받은 수열 번째가 count보다 작아질 때까지 돌도록 만들었습니다. count가 해당 괄호의 마지막 수열이니 count가 커지는 순간 그 수열이 해당 괄호에 있다는 의미가 됩니다. while문 안에서는 count = count + i를 통해 count(앞 수열의 괄호의 마지막 수열 번째) + 현재 괄호 번호 를 해주어서 count가 다음 괄호의 마지막 수열 차례를 알 수 있도록 합니다. i++를 통해 다음 괄호를 계산할 준비를 합니다.

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

 

count는 괄호의 마지막 수열을 의미하고 i는 괄호의 차례이자 최댓값을 나타냅니다. 이 정보를 가지고 해당 수열의 분모와 분자를 알아낼 수  있습니다. 짝수 일 때는 1에서부터 해당 괄호의 마지막 부분(count)에서 수열의 첫 값만큼 분모의 넣어주면 되고 분자에는 최댓값에서 마지막 부분에서 해당 수열의 차만큼 빼주면 됩니다. 반대로 홀수 일 때는 역시 분모와 분자만 변경해서 초기화시켜 주면 됩니다.

if((i-1)%2 == 0) {
	deno = 1 + (count - x);
	numer = (i-1) - (count-x);
}else {
	deno = (i-1) - (count-x);
	numer = 1 + (count - x);
}
		
		
System.out.println(numer  + "/" + deno);

 

잘 이해가 되지 않는 부분이 있으면 댓글을 달아주세요.

직관적으로 보이면 어렵지 않은데 글로 설명하려니 생각보다 어렵네요.