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

▶ 문제

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

1193번: 분수찾기

▶ 설명

 

지그재그 순으로 나열한 것을 배열로 표현해 보았다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1/1	1/2	2/1	3/1	2/2	1/3	1/4	2/3	3/2	4/1	5/1	4/2	3/3	2/4	1/5	1/6	2/5

색깔별로 구분해 놓았 듯이 나름 규칙이 보인다.

 

분모만 살펴보면 규칙을 더 한눈에 볼 수 있다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	1	2	3	2	1	1	2	3	4	5	4	3	2	1	1	2

인덱스가 0, 1~ 2, 3~ 5, 6~ 9, 10~14, ... 를 지날때 마다 1, 2, 3, 4, 5, .. 개의 숫자가 순차적으로 1부터 나열되어 있는 것을 볼 수 있다.

다만 문제에서의 '지그재그'란 표현처럼 번갈아가면서 수열이 역방향, 정방향으로 되어 있다는 점이 특징이다.

게다가 분자는 분모와 반대 방향으로 간다.

이러한 특징을 캐치하니 코드로 옮기는 것은 어렵지 않게 할 수 있었다.

 

 

▶ 문제 풀이

🌱 풀이.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int count = 0;
		int copyN = n; // 입력받은 수를 카피
		if (n == 1) {
			count = 1;
		} else {
			while (n > 0) {
				n = n - (1 * (count + 1));
				count++;
			}
		}

		// 최대값 구하기.
		int max = 0;
		for (int i = 1; i <= count; i++) {
			max += i;
		}

		// 짝수일 때
		int numer = 0; // 분자 numerator
		int denomi = 0; // 분모 denominator
		if (copyN == 1) {
			numer = 1;
			denomi = 1;
		} else if (count % 2 == 0) {
			numer = count - (max - copyN);
			denomi = (max - copyN) + 1;
		} else if (count % 2 == 1) {
			numer = (max - copyN) + 1;
			denomi = count - (max - copyN);

		}
		System.out.println(numer + "/" + denomi);
	}

}

 

 

 

 

▶ Log