[백준] 1193번 : 분수찾기 - JAVA [자바]

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

1193번: 분수찾기

---

• 문제

 

 

 

 

분수를 찾는 것 자체는 그렇게 어려운 문제는 아니다.

다만 순서에 유의하여야 한다.

---

• 2가지 입력방법을 이용하여 풀이한다.

 

 

Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다.

 

---

• 알고리즘

앞서 언급했듯이 분수를 찾는 것은 그렇게 어려운 문제가 아니다.

어떤 칸에 어떤 분수인지는 그림만 보더라도 바로 나온다.

 

분모 값과 분자 값의 합을 T 라고 할 때 다음과 같은 규칙이 생긴다.

 

 

 

그리고 대각선 칸의 개수는 T - 1 개다.

 

 

그러면, X 번째의 분수는 어떻게 찾아야 하는가가 문제다.

문제에서 순서는 다음과 같다고 명시되어 있다.

 

1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 

 

즉, 위 그림으로 치면 다음과 같다.

 

파란색 ( T 가 짝수, 또는 대각선 칸의 개수가 홀수 ) 일 때는 왼쪽 아래에서 오른쪽 위 방향 ( ↗︎ ) 으로 진행되고,

빨간색 ( T 가 홀수, 또는 대각선 칸의 개수가 짝수 ) 일 때는 오른쪽 위에서 왼쪽 아래 방향 ( ↙︎ ) 으로 진행된다.

 

즉, T % 2 가 0 일 때는 대각선 위 방향, 1 일 때는 아래 방향으로 진행된다는 것.

 

그럼 우리가 이용할 변수는 다음과 같다.

 

1. 입력받을 X 값
2. 해당 범위의 대각선 칸 개수 ( cross_count )
3. 해당 대각선 직전 대각선 까지의 칸의 누적 합 ( prev_count_sum )

 

 

 

이렇게 3 개를 이용하여 X 값이 해당 범위의 값이 나올 때 까지 반복하고,

 

만약 해당 범위의 값이라면

대각선의 개수가 홀수인지, 짝수인지 판별하여 해당 대각선의 첫 원소와 X, 대각선의 개수를 이용하여 분모 분자 값을 구해준다.

 

말로하면 잘 이해가 안될테니 코드를 한 번 보자.

---

• 풀이

- 방법 1 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		int X = in.nextInt();

		int cross_count = 1, prev_count_sum = 0;

		while (true) {
        
			// 직전 대각선 누적합 + 해당 대각선 개수 이용한 범위 판별
			if (X <= prev_count_sum + cross_count) {	
				
				if (cross_count % 2 == 1) {	// 대각선의 개수가 홀수라면 
					// 분자가 큰 수부터 시작
					// 분자는 대각선상 내의 블럭 개수 - (X 번째 - 직전 대각선까지의 블럭 개수 - 1) 
					// 분모는 X 번째 - 직전 대각선까지의 블럭 개수
					System.out.print((cross_count - (X - prev_count_sum - 1)) + "/" + (X - prev_count_sum));
					break;
				} 
				
				else {	// 대각선상의 블럭의 개수가 짝수라면 
					// 홀수일 때의 출력을 반대로 
					System.out.print((X - prev_count_sum) + "/" + (cross_count - (X - prev_count_sum - 1)));
					break;
				}

			} else {
				prev_count_sum += cross_count;
				cross_count++;
			}
		}
	}
}

 

 

즉, 직전 대각선까지의 누적합과 X 의 차이를 이용하면 해당 대각선에서 몇 번째의 분수인지 알 수 있고,

이를 대각선의 개수를 이용하여 짜면 쉽게 짤 수 있는 알고리즘이다.

 

(만약 이해 안된다면 댓글 달아주세요..)

---

- 방법 2 

BufferedReader 을 쓰는 방식이다.

 

그리고 반드시 자료형 타입을 잘 보아야 한다.

br.readLine() 은 문자열로 데이터를 읽으니 반드시 꺼내서 쓸 때 int 형으로 쓰고자 한다면 Integer.parseInt()로 String 을 int 형으로 변환시켜준다.

 

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

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 cross_count = 1, prev_count_sum = 0;

		while (true) {
			// 직전 대각선 누적합 + 해당 대각선 개수 이용한 범위 판별
			if (X <= prev_count_sum + cross_count) {	
				
				if (cross_count % 2 == 1) {	// 대각선의 개수가 홀수라면 
					// 분자가 큰 수부터 시작
					// 분자는 대각선상 블럭의 개수 - (X 번째 - 직전 대각선까지의 블럭 개수 - 1) 
					// 분모는 X 번째 - 직전 대각선까지의 블럭 개수
					System.out.print((cross_count - (X - prev_count_sum - 1)) + "/" + (X - prev_count_sum));
					break;
				} 
				
				else {	// 대각선의 개수가 짝수라면 
					// 홀수일 때의 출력을 반대로 
					System.out.print((X - prev_count_sum) + "/" + (cross_count - (X - prev_count_sum - 1)));
					break;
				}

			} else {
				prev_count_sum += cross_count;
				cross_count++;
			}
		}
	}
}

 

 

 

위 코드는 알고리즘은 똑같으나, 시간을 줄이는 것에 의미를 두는 분들을 위해 BufferedReader 을 쓴 것이다.

당연 성능은 Scanner 에 비해 BufferedReader 가 압도적으로 좋다.

 

---

• 성능 차이

 

위에서 부터 순서대로

 

채점 번호 : 18820208  -  BufferedReader 

채점 번호 : 18820203  -   Scanner 

---

• 정리

 

이번 문제는 아예 문제만 보더라도 규칙이 너무 쉽게 보이는 문제라 그리 어려운 것이 없었다.

 

그래도 혹여 잘 이해가 안되시는 분들이 있다면 댓글로 남겨주시면 감사하겠다.