[백준 1193번] 분수찾기

백준알고리즘 1193번 : 분수찾기

 

어떻게 접근하는 지 알게되고나면 어렵지 않은 문제라고 생각한다.

그러나 언제나 그 접근 방법이 어렵다.

 

분모와 분자의 합을 S라고 하자,

이 X를 기준으로 1행(혹은 1열)을 보게되면, {2, 3, 4, 5,....} 와 같이 한 개씩 늘어나는 것을 확인할 수 있다.

그리고 행을 기준으로 왼쪽 아래의 대각선으로 한칸씩 내려가면,

하나의 대각선은 모두 동일한 S값을 갖고 있음을 알 수 있다.

 

그렇다면 우리가 구하고자하는 N번째 수가 1행의 몇 번째 열에 해당하는 대각선에 있는지 알 수 있다면,

적절한 계산을 통해 구할 수 있을 것이다.

 

각 대각선의 길이는 1, 2, 3...순으로 1씩 증가하는 등차수열이므로,

등차수열의 합 공식 n(n+1)/2  을 이용하여 대각선 길이의 총 합이 구하고자하는 X 값보다 커지는 지점을 확인하고,

이를 보정해주면 되겠다.

 

 

풀이 과정

---

1. 등차수열의 합 n(n+1)/2 공식을 이용하여,
  대각선의 총 합이 구하고자하는 X보다 크거나 같을 때의 대각선 길이 n을 구한다.
  X는 즉 n번째 대각선 어딘가에 있을 것이며, 이를 보정해주어야한다.
2. 대각선의 길이 n이 짝수면, 첫 row(마지막 column)부터 셈이 이뤄지고
   대각선의 길이 n이 홀수면, 마지막 row(첫 column)부터 셈이 이뤄진다.
3. 이에 맞추어 적절한 출력을 해준다.

 

 

 

 

소스 ▽

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int num = sc.nextInt();
		int count = 0;
		int length = 0;//대각선의 길이
		while (count<num) { 
			length++;
			count = length *(length+1) / 2;
		}//대각선의 총 합이 구하고자하는 수의 번째보다 크거나 같으면 stop.
		//즉 우리의 num은 마지막 length만큼의 대각선 사이에 있을 것이다.

		//해당 대각선까지의 총함 - 구하고자하는 X번째 만큼을 보정해주어야한다.
		int move = count-num;
		//length가 짝수면, 첫 row(마지막 column)부터 셈이 이뤄지고,
		//length가 홀수면, 마지막 row(첫 column)부터 셈이 이뤄진다. 
		if (length%2==0) {
			System.out.println((length-move)+"/"+(1+move));
		}else {
			System.out.println((1+move)+"/"+(length-move));
		}
	}

}

 

 

 

Summary

---

등차수열의 합 S =n(n+1)/2