[BOJ] 백준 1193번: 분수찾기 _자바(JAVA)

1. 문제

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

 

---

2. 접근 및 해결

2-1) 접근

문제를 해결하기 위해 총 4가지를 신경써야합니다.

풀이 이해를 쉽게 하기 위해 Input을 8이라 가정, Output인 2/3을 찾아야하는 경우를 알아보겠습니다.

아래의 노트를 띄워놓고 설명을 봐주세요!

풀이 노트

 

1. 방문 순서

방문 순서는 문제에서 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서라고 나와있습니다.

이를 쉽게 다시 생각해보면,

1/1,

1/2 -> 2/1,

3/1 -> 2/2 -> 1/3 의 순서로 파란색 대각선 막대기처럼 계속 이동하는 것을 알 수 있습니다.

그리고 우리가 찾아야하는 8번째 값은 이렇게 따라가다보면 2/3임을 알 수 있습니다.

 

2. 개수

개수는 하나의 파란색 대각선 막대기 당 몇 개의 분수들이 들어가있는지를 나타냅니다.

우리가 찾는 8번째 값인 2/3은 개수=4임을 알 수 있습니다.

개수라고 하기에는 헷갈리니까, 4번째 줄이라고 생각합시다.

 

3. 대각선의 합

각각의 대각선의 합은 개수+1임을 볼 수 있습니다.

우리가 찾는 8번째 값인 2/3은 합이 5인 구간에 위치하고 있습니다.

 

4. 홀수번째 줄? 짝수번째 줄?

위에서 2. 개수를 설명할 때 4번째 줄이라고 생각하자고 했었습니다.

굳이 그렇게 한 이유는 방문순서에서 쓰였던 파란색 대각선 막대기를 기준으로 1줄씩 봤을 때, 

홀수번째는 감소/증가하는 형태를 띄고 있고, 짝수번째는 증가/감소하는 형태를 띄고 있습니다.

 

우리가 찾는 8번째 값인 2/3은 증가/감소하는 구간에 위치하고 있군요.

좀 더 쉽게 설명하자면,

4번째 줄은 1/4 -> 2/3 -> 3/2 -> 4/1입니다.

분자는 1 -> 2 -> 3 -> 4로 증가하고 있고, 분모는 4 -> 3 -> 2 -> 1의 형태로 감소하고 있지요.

 

---

2-2) 해결

이제 신경써야하는 4가지에 대해 모두 알게 되었는데, 그래서 코드로 어떻게 해결할지를 알아봅시다.

예시 Input인 X는 8입니다.

즉, 8 = 1+2+3+2이지요.

왜 마지막에 +2를 해두었냐? 우리는 8=(1+2+3)+2로 보아야합니다.

앞에서 개수는 1, 2, 3, 4로 증가함을 알게 되었는데 여기서 괄호 안에 있는 값의 수가 (개수값-1)입니다.

왜 -1이냐면 괄호 밖에 있는 +2로 인해 개수값이 +1이 되기 때문이지요.

 

결국 우리가 찾는 2/3은 4번째에 위치하고,

앞서 알아본 4가지를 종합해서 보았을 때 2/3은 합이 5인 구간에서 2번째 순서임을 알 수 있습니다.

 

합이 5인구간에서 2번째 순서란? (+개수 값이 짝수(4)임)

1/4, 2/3, 3/2, 4/1에서 2/3 임을 알 수 있습니다.

---

3. 코드(JAVA) 

코드와 관련된 설명은 상세히 주석으로 달아두었습니다.

위에서 작성한 접근 및 해결을 읽어보시고 읽어주세요!

import java.io.*;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int X = Integer.parseInt(br.readLine());
		int num = 0;
		
		// X가 1이거나 2인 경우 아래의 for문 내 if문에 접근하지 못하므로 따로 처리
		if(X==1) {
			bw.write("1/1");
		} else if(X==2) {
			bw.write("1/2");
		}
		
		// ex) X=8인 경우에 대해 생각해보면
		 for(int i=1; i<X; i++) {
			 num += i; // 1+2+3+4

			 if(num >= X) { // i가 4일때, 10 >= 8 이므로 if문 실행됨
				 num -= i; // 10은 구하려는 숫자가 아니므로 다시 4를 빼줌
				 		   // num = 6(1+2+3)
				 int sequence = X - num; // sequence(순서) = 8-6 = 2
				 
				 // 여기까지 생각했을 때
				 // X(8) = num(6) + sequence(2)
				 // i = 4
				 // 합이 5인 구간에서 2번째 순서, 5(i+1) - sequence(2) = 3

				 if(i%2==0) { // 짝수 구간, 8은 짝수구간이므로 if문 실행됨
					 // 짝수는 증가/감소 구간
					 bw.write(sequence+"/"+((i+1)-sequence)); // 2/3 출력 
				 } else { // 홀수 구간
					 // 홀수는 감소/증가 구간
					 bw.write(((i+1)-sequence)+"/"+sequence);
				 }
				 break;
			 }
		 }
		
		br.close();
		bw.close();
	}
}