백준 (1193번: 분수찾기)_Java
제목: 분수찾기
브론즈 1
문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
| 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/2 2/1
3그룹: 3/1 2/2 1/3
4그룹: 1/4 2/3 3/2 4/1
홀수 그룹은 분자가 감소하고 분모가 증가한다.
짝수 그룹은 분자가 증가하고 분모가 감소한다.
step1) 입력받은 숫자의 분수가 몇 그룹인지 알아야 한다.
int n=0;
int cnt=0;
while(cnt<X){
n++;
cnt=n*(n+1)/2; //몇번 째 행인지 찾는 코드
}
cnt=n*(n+1)/2의 공식으로 몇 번째 그룹인지 알 수 있다.
예를 들어 X=5라고 하자,
n=1 cnt=1*(1+1)/2 cnt=1 1/1
n=2 cnt=2*(2+1)/2 cnt=2 1/2 2/1
n=3 cnt=3*(3+1)/2 cnt=6 1/1 1/2 2/1 3/1 2/2 1/3 총 여섯 개 n=3번째 그룹
step 2) 그룹의 몇 번째 값인지 찾는 코드.
int num=X-(n-1)*n/2; //행의 몇번 째 값인지 찾는 코드
X=5 일 때, 5-(3-1)*3/2 (n==3인 이유는 위에 코드를 보자)
따라서 num=2
3번째 그룹 2번째 값은 2/2라는 것을 파악
step3) 최종 구현 홀수 그룹과 짝수 그룹을 나누어서 구현
if(n%2==0) { //짝수 행일 시
top=num;
bot=n-num+1;
}else {
top=n-num+1;
bot=num;
}
System.out.println(top+"/"+bot);홀수 그룹은 분자가 감소하고 분모가 증가한다.
짝수 그룹은 분자가 증가하고 분모가 감소한다.
🔑코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
public static void main(String args[])throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int X=Integer.parseInt(br.readLine());
int n=0;
int top=1;
int bot=1;
int cnt=0;
if(X==1) {
System.out.println("1/1");
}else {
while(cnt<X){
n++;
cnt=n*(n+1)/2; //몇번 째 행인지 찾는 코드
}
int num=X-(n-1)*n/2; //행의 몇번 째 값인지 찾는 코드
if(n%2==0) { //짝수 행일 시
top=num;
bot=n-num+1;
}else {
top=n-num+1;
bot=num;
}
System.out.println(top+"/"+bot);
}
}
}
알고리즘 분류
https://www.acmicpc.net/problem/1193
1193번: 분수찾기
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
www.acmicpc.net
커버 사진