[백준알고리즘/기본 수학 1단계] 1193번 문제 : 분수찾기(자바/JAVA)

안녕하세요

백준 알고리즘 단계별로 풀어보기 8단계 1193번 문제 분수찾기를 풀어봤습니다

처음 원리를 파악하는 것은 어렵지 않은데 이걸 프로그래밍으로 구현을 하려니 생각이 많아지던 문제였습니다

제가 풀은 방법 한 개와 다른 분들이 풀은 문제를 참고해 작성한 코드 두 개에 대해서 설명하겠습니다

 

---

문제 링크입니다

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

1193번: 분수찾기

 

문제

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

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)가 주어진다.

 

출력

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

 

 

---

 

 

문제 풀이

먼저 알고리즘을 파악해야합니다

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 -> 2 -> 3 -> 4 -> 5 -> 6 자릿수가 한 개 증가할 때 총 갯수는 

1 -> 3 -> 6 -> 10 -> 15 -> 21 로 증가가 됩니다

갯수가 1씩 증가하고 있습니다

 

짝수의 경우 분모는 1에서 시작, 홀수의 경우 분자가 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 선언 및 N 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		int N = Integer.parseInt(br.readLine());
		
		// 분모, 분자 및 Sum, 이전Sum, Count 선언
		int a10, a1;
		int sum = 0;
		int pre_sum = 0;
		int count = 0;
		
		// 반복문을 사용하여 Count갯수와 Sum, 이전Sum을 구한다
		// Sum이 N보다 커지면 반복문 종료
		while(sum < N)
		{
			count++;
			pre_sum = sum;
			sum += count;
		}

		// Count가 짝수인 경우 분자 1부터 시작, 홀수인 경우 분모 1부터 시작
		if(count % 2 == 0)
		{
			a10 = 1;
			a1 = count;
		}
		else 
		{
			a10 = count;
			a1 = 1;
		}
		
		// 반복문을 사용 짝수인 경우 분자++, 분모-- // 홀수인 경우 분자--, 분모++
		for(int i = pre_sum + 1; i < N; i++)
		{
			if(count % 2 == 0)
			{
				a10++;
				a1--;
			}
			else 
			{
				a10--;
				a1++;
			}
		}
		
		// 결과 출력
		System.out.print(a10 + "/" + a1);
	}
}

 

---

두 번째 방법은 이 글을 참고한 방법입니다

https://www.acmicpc.net/source/23950830

반복문을 사용 N에서 Count를 더한값을 계속 뺀 값이 분모/분자가 됩니다

이어서 위의 값을 거꾸로 뒤집은 count+1-N을 한 값이 분모/분자가 됩니다

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

public class Main { 
	public static void main(String[] args) throws IOException {
		// BufferedReader, StringBuffer 선언 및 N 입력	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		int N = Integer.parseInt(br.readLine());
		
		// 갯수를 구할 Count
		int count = 1;
		
		// 반복문을 사용 N이 Count보다 작아지면 반복문 종료
		while(N > count) {
			N -= count++;
		}
		
		// 짝 수인 경우
		if(count % 2 == 0) {
			// N이 분자, count+1-N 분모
			sb.append(N).append("/").append(count+1 - N);
		// 홀 수인 경우
		}else {
			// count+1-N 분자, N이 분모
			sb.append(count+1 - N).append("/").append(N);
		}
		
		// 결과 출력
		System.out.print(sb.toString());	
	}
}

 

여기까지 두 가지 방법으로 풀어봤습니다

이제 속도비교를 해보겠습니다

 

---

 

속도 비교

2번 방식이 압도적으로 메모리와 시간이 더 적게 걸렸습니다 ㅎ

 

1193번 풀은 결과입니다

등수가 1등으로 나와 자랑겸 올려봅니다!!

 

이상 백준 알고리즘 1193번 분수찾기를 풀은 내용이었습니다

 

다음 문제 : 2021.05.24 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 1단계] 2869번 문제 : 달팽이는 올라가고 싶다(자바/JAVA)

이전 문제 : 2021.05.22 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 1단계] 2292번 문제 : 벌집(자바/JAVA)