[백준알고리즘] 1193번 분수찾기 (JAVA)

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

 

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

 

예제

 

풀이

public class Main {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		
		int line=1; // 해당 라인에 존재 하는 값
		int cnt=0; // 현재 갯수
        
        	// n번째 분수가 몇번째 라인에 있는지 구하기
		while(true){
            		if(cnt+line>=n){ 
            			break;
           		}
			cnt += line;
			line++;
		}
        
        	// 해당 라인에서 몇 번째인지 구하기 n-cnt
		int th = n - cnt;
		
        	// 홀수 짝수 조건 구분
		if(line % 2 == 0) { 
			System.out.println(th+"/"+(line-th+1));
		} else { 
			System.out.println((line-th+1)+"/"+th);
		}
	}
}

1. n번째 분수가 몇 번째 라인인지 구하기

X번째 분수가 몇 번째 대각선에 위치하는지 알아야한다. 

1 : 1/1  2 : 1/2 2/1  3 : 3/1 2/2 1/3 4 : 1/4 2/3 3/2 4/1 5 : 5/1 4/2 3/3 2/4 1/5 ...

 

2. IF 짝수 그룹, 홀수 그룹

라인이 홀수인지 짝수인지에 따라 숫자(분모,분자)의 순서가 바뀌므로 if문 처리를 해야한다.
1) line이 홀수일 경우 : 분모는 1부터 증가 / 분자는 큰 수부터 시작
2) line이 짝수일 경우 : 분모는 큰 수부터 시작 / 분자는 1부터 증가

 

참고

iamheesoo.github.io/blog/algo-boj1193

[JAVA/백준] 수학 1: 분수찾기

 

출처

www.acmicpc.net/problem/1193

1193번: 분수찾기