#1193 : 분수찾기

풀이방법

사용된 것:

수학

 

2022.05.01

가장 왼쪽 위의 대각선을 첫 번째 대각선이라 하고 오른쪽 아래로 갈수록 2, 3, 4, ... 번째 대각선이라 하자.

 

입력값으로 N이 주어진다.

 

N번째 수가 몇 번째 대각선에 속하는지를 먼저 구하고,

그 대각선 내에서 몇 번째의 수인지를 구하면 된다.

이 두 가지만 알면 분수를 정확하게 구할 수 있다.

 

 

몇 번째 대각선에 속하는지 구하는 방법은 다음과 같다.

 

1번째 대각선부터 k번째 대각선까지에 속하는 분수의 개수는 1부터 k까지의 정수를 더한 것과 같다.

따라서, 1부터 k까지 더했을 때의 합이 N보다 크거나 같은 가장 작은 k를 찾으면 된다. N은 이 k번째 대각선에 속한다.

 

 

k번째 대각선 내에서 몇 번째의 수인지를 구하는 법은 다음과 같다.

 

1~k의 정수를 더한 합보다 N이 얼마나 작은지를 구하면 된다.

(1 + 2 + ... + k) - N = 0이라면 N번째 분수는 k번째 대각선 내에서 순서가 가장 느린 수이고 (뒤에서 1번째)

(1 + 2 + ... + k) - N = 1이라면 순서가 두 번째로 느린 수이고 (뒤에서 2번째)

(1 + 2 + ... + k) - N = 2라면 순서가 세 번째로 느린 수이다. (뒤에서 3번째)

 

1~(k-1)의 정수를 더한 것보다 N이 얼마나 큰지를 구해도 된다.

N - (1 + 2 + ... + (k-1)) = 1이라면 그 수는 k번째 대각선 내에서 순서가 가장 빠른 수이고 (앞에서 1번째)

N - (1 + 2 + ... + (k-1)) = 2라면 순서가 두 번째로 빠른 수이고 (앞에서 2번째)

N - (1 + 2 + ... + (k-1)) = 3이라면 순서가 세 번째로 빠른 수이다. (앞에서 3번째)

 

 

이렇게 몇 번째 대각선에 속하는지와 그 대각선 내에서 몇 번째 수인지를 구했으면 다음의 원리를 이용해 분수를 찾을 수 있다.

 

k가 짝수일 때에는 해당 대각선에서 제일 오른쪽 위에 있는 수가 가장 순서가 빠르다.

즉 가장 순서가 빠른 분수의 (분모)-(분자)의 값이 k-1이다. 가장 순서가 느린 왼쪽 아래의 수는 반대로 (분자)-(분모)의 값이 k-1이다.

k가 홀수일 때에는 해당 대각선에서 제일 왼쪽 아래에 있는 수가 가장 순서가 빠르다.

즉 가장 순서가 빠른 분수의 (분자)-(분모)의 값이 k-1이다. 가장 순서가 느린 오른쪽 위의 수는 반대로 (분모)-(분자)의 값이 k-1이다.

 

이를 이용하여, 해당 대각선에서 가장 순서가 빠른/느린 분수를 알아낼 수 있다. 가장 순서가 빠른/느린 수의 분자와 분모에서 수를 적절히 빼고 더해주면 정답이 도출된다.

 

예를 들어 N이 9인 경우 다음과 같이 구하면 된다.

 

1 + 2 + 3 = 6 이고

1 + 2 + 3 + 4 = 10 이므로

9번째 수는 4번째 대각선에 있고, 

10 - 9 = 1

9 - 6 = 3

이므로 4번째 대각선의 분수들 중 뒤에서 두 번째, 즉 앞에서 3번째이다.

 

4가 짝수이므로, 4번째 대각선에서 1번째인 수는 오른쪽 위의 수인 1/4이다.

3번째 분수는 1번째 분수의 분자와 분모에 (3 - 1)의 값인 2를 더하고 빼주면 된다.

분자는 1에 2를 더한 3이고 분모는 4에서 2를 뺀 2이다.

답은 3/2이다.

 

코드

Java(2022.05.01)

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		//몇 번째 대각선에 속하는지 알아내기
		int sum = 0;
		int num = 0;
		while(true) {
			sum += ++num;
			if(sum>=n) break;
		}
		//n번째 수는 num번째 대각선에 속함
		
		//sum에서 n을 빼면 해당 대각선 내에서 몇 번째 수인지 알 수 있음
		int sub = sum - n;
		int up, down = 0;	//분자와 분모
		
		//num이 짝수인 경우
		if(num%2 == 0) {
			up = num-sub;	//분자
			down = 1 + sub;	//분모			
		}
		
		//num이 홀수인 경우
		else {
			up = 1 + sub;	//분자
			down = num-sub;	//분모
		}
		
		//답 출력
		System.out.print(up + "/" + down);
	}

}