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

 

 

<코드>

import java.util.*;
import java.util.PrimitiveIterator.OfDouble;
public class Main {
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int X = sc.nextInt();
		int layer = 1;
		int x,y; // 정답 좌표
		
		while (true) {
			if(layer*(layer+1)/2 >= X) {
				
				if(layer % 2 == 0) {// 층이 짝수 일 경우
					x = X-layer*(layer-1)/2; // layer*(layer-1)/2은 layer-1층까지의 분수들의 개수
					y = layer+1-x;
				}
				else{ // 층이 홀수 일 경우
					y = X-layer*(layer-1)/2; // layer*(layer-1)/2은 layer-1층까지의 분수들의 개수
					x = layer+1-y;
				}
				
				System.out.println(x+"/"+y);
				
				break;
			}
			layer++;
		}
		
	}
}

 

풀이 방법

 

 

표의 숫자는 X번째 수입니다.

layer(층)이 짝수일 때는 우측 상단에서 좌측 하단으로 수가 채워지며, (↙)

layer(층)이 홀수일 때는 좌측 하단에서 우측 상단으로 수가 채워집니다. (↗)

 

코드에서 while문을 통해서 layer를 증가시키면서 X가 몇 층인지 알아냅니다.

X가 만약 14라고 가정할 때

• 14의 layer는 5입니다.
• layer가 홀수입니다. 
• layer가 홀수일 때는 좌측 하단에서 우측 상단으로 분수가 채워집니다. (↗)
• layer - 1까지의 수의 개수는 layer * (layer - 1) / 2로 구할 수 있으며,
  layer = 5 이므로 layer가 4까지의 분수의 개수는 10입니다.
• X는 5층에서 X-10 = 14 - 10 = 4번째 수입니다.
• 따라서 5층의 첫 번째 분수가 "5/1" 이므로 4번째 분수는 "2/4"가 됩니다.

 

 

 

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

1193번: 분수찾기