안녕하세요
백준 알고리즘 단계별로 풀어보기 8단계 1193번 문제 분수찾기를 풀어봤습니다
처음 원리를 파악하는 것은 어렵지 않은데 이걸 프로그래밍으로 구현을 하려니 생각이 많아지던 문제였습니다
제가 풀은 방법 한 개와 다른 분들이 풀은 문제를 참고해 작성한 코드 두 개에 대해서 설명하겠습니다
문제 링크입니다
https://www.acmicpc.net/problem/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)
'알고리즘 > 알고리즘JAVA' 카테고리의 다른 글
[백준알고리즘/기본 수학 1단계] 10250번 문제 : ACM 호텔 (0) | 2021.05.25 |
---|---|
[백준알고리즘/기본 수학 1단계] 2869번 문제 : 달팽이는 올라가고 싶다(자바/JAVA) (0) | 2021.05.24 |
[백준알고리즘/기본 수학 1단계] 2292번 문제 : 벌집(자바/JAVA) (0) | 2021.05.22 |
[백준알고리즘/기본 수학 1단계] 1712번 문제 : 손익분기점(자바/JAVA) (0) | 2021.05.22 |
[백준알고리즘/문자열] 1316번 문제 : 그룹 단어 체커(자바/JAVA) (0) | 2021.05.20 |