백준 알고리즘 1193번 문제 풀이 - 분수 찾기

 

처음 문제를 봤을 때 무슨 소리인지 한참 봤다...

아래의 사진을 보면 이해가 조금 될 것이다

 

지그제그 순서대로 번호가 있는 것이다.

14번 째 방에는 2/4가 있기 때문에 14를 입력 받으면 2/4가 출력되는 것이다.

 

이 문제를 보고 규칙을 찾으려고 한참을 생각하였다.....

 

분수(분자, 분모)를 구하기 위해서는 전체 데이터의 갯수와 라인의 수, 데이터의 방향(?)이 필요하다.

일단 하나씩 구하고 어디에 쓰는지 보자!

 

아래의 그림을 대각선으로 보면 데이터의 수가 1씩 증가한다.

1번째 라인은 1개, 2번째 라인은 2개, ....5번째 라인은 5개, ...

이것을 통해 총 데이터의 갯수를 구할 수 있다.

 

또, 아래의 그림을 보면 분자 또는 분모가 라인의 수와 같고, 홀수일경우 ↗쪽으로 짝수의 경우 ↙쪽으로 방의 수가 증가한다.

그리고, n번째 줄의 첫번째 수와 마지막 수는 분자와 분모의 위치만 다르고, 분자와 분모의 합이 라인수 + 1 인것을 알 수 있다.

이제 몇 번째 라인인지 찾은 뒤 분자와 분모가 될 숫자 a,b를 구하여 출력만 해주면 된다.

 

이제 구한 총 데이터의 갯수(sum)와 line의 수가 필요하다.

a : 몇 번째 라인의 몇 번째 데이터인지 = line-(sum-N) 

이제 b를 구할 차례이다 a+b = 라인수+1 이기 때문에 라인수 + 1 - a를 해주면 b를 구할 수 있다.

b : 라인수 + 1 - a = line+1-a;

마지막으로 출력만 해주면 되는데 라인이 짝수일 경우 분자는 a 분모는 b 반대로 홀수일 경우에는 분자는 b 분모는 a가 된다.

 

ex) N=14일 경우 a = 5 - (15-14) = 4

                       b = 5 + 1 - 4 = 2

                       ↗ 방향일때는 홀수이므로 a/b이므로 답은 2/4이다.

자바

import java .util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();
		int sum=0;
		int line=1;
		
		while(true){
			sum+=line;
			if(N<=sum){
				int a = line-(sum-N);
				int b = line+1-a;
				if(line%2==0){
					System.out.println(a+"/"+b);
				}else{
					System.out.println(b+"/"+a);
				}
				break;
			}
			line++;
		}
	}
}

if(N<=sum) : N이 해당 라인에 있는 방 번호인지 알아내기 위한 조건문