[백준/JAVA] 1193번: 분수 찾기

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

1193번: 분수찾기

import java.io.*;

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 cnt = 0; // 개수
		int line = 0; // 행 번호
		
		while(cnt < x) { 
			line++;
			cnt = line * (line+1) /2;
		}
		
		if(line%2 != 0) {
			System.out.print((1+cnt-x) + "/" + (line+x-cnt));
		} else {
			System.out.print((line+x-cnt) + "/" + (1+cnt-x));
		}
		   
    }
}

 

1/1 → 1/2 → 2/1 → 3/1 → 2/2 → …

 

1/1(1)

1/2(2) 2/1(3)

3/1(4) 2/2(5) 1/3(6)

1/4(7) 2/3(8) 3/2(9) 4/1(10)

 

각 행의 마지막 번호 = 행*(행+1)/2

 

분모+분자 = 행+1

 

홀수 행 기준

• 분자: 1+(각 행의 마지막 번호)-본인의 번호
• ex) 3/1(4) ⇒ 1+6-4 = 3
• 분모: 행+1-분자 = 행+1-1-(각 행의 마지막 번호)+본인의 번호 = 행-(각 행의 마지막 번호)+본인의 번호
• 짝수행은 분모와 분자 반대로 적용