본문 바로가기
Algorithm/Baekjoon

Baekjoon 1193 분수찾기 JAVA

by Hunveloper 2022. 1. 27.
728x90
 

1193번: 분수찾기

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

www.acmicpc.net

문제

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

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번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

풀이

각 대각선의 분자, 분모의 합은 2,3,4 처럼 1씩 증가하고, 그렇게 생성된 배열은 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6... 이러한 형태를 가진다. 또한 각 합마다 분자, 분모의 순서가 바뀌기에 두가지를 체크해야한다. 

먼저 2부터 시작해 1씩 증가하는 배열을 만들고 값이 증가할때마다 방향이 바뀐다고 생각하고, evenodd를 체크하여 분모가 큰지 분자가 큰지를 결정한다.

코드
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int cnt = 0, i = 0;
		boolean evenodd=false;
		while (cnt < n) {
			i++;
			evenodd=!evenodd;
			for (int j = 0; j < i; j++) {
				cnt++;
				if(cnt>=n)	{
					if(evenodd)
						System.out.println(String.valueOf(i-j)+"/"+String.valueOf(j+1));
					else
						System.out.println(String.valueOf(j+1)+"/"+String.valueOf(i-j));
					break;
				}					
			}			
		}		
	}
}
728x90
728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

Baekjoon 14647 준오는 조류혐오야!! JAVA  (0) 2022.01.28
Baekjoon 4732 조옮김 JAVA  (0) 2022.01.28
Baekjoon 11723 집합 JAVA  (0) 2022.01.27
Baekjoon 1676 팩토리얼 0의 개수 JAVA  (0) 2022.01.27
Baekjoon 1996 지뢰 찾기 JAVA  (0) 2022.01.27

댓글