출처: https://bumcrush.tistory.com/182 [맑음때때로 겨울]
반응형

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

 

1193번: 분수찾기

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

www.acmicpc.net

 

import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int X = sc.nextInt();
int cnt = 0;
boolean flag = false;
//짝수 분자 증가(위,아래) , 홀수 분자 감소(아래,위)
for(int i=1; i <= 10000000; i++){
if(flag) return;
cnt += i;
if(cnt >= X){
cnt -= i;
int a = 1;
int b = i;
while(true){
cnt++;
if(cnt == X){
if(i % 2 ==0){
System.out.println("" + a + "/" + b);
}else{
System.out.println("" + b + "/" + a);
}
flag = true;
return;
}else{
a++;
b--;
}
}
}
}
}
}

 

1. 풀이

규칙을 먼저 찾아야 한다. 규칙은 대각선방향으로 순서대로 움직임 

 

1 : 1/1

2 : 1/2 , 2/1

3 : 3/1, 2/2, 1/3 

4 : 1/4, 2/3, 3/2, 4/1

 .........

 

짝수는 위에서 아래로 홀수그룹은 아래에서 위로 움직이게 된다.

 

1. 어떤그룹인지 먼저 찾는다. 

 - 1부터 ~ 10000000 까지 loop 돌면서 합이 X와 크거나 같은 그룹을 찾는다. 

2. 같은 그룹을 찾게 되면 해당 그룹을 loop 돌면서 입력받은 값과 같은 번호를 찾는다.

  - a 는 1번부터 증가, b는 그룹 번호 부터 감소시켜 나간다. 

  - 홀수는 b/a 짝수는 a/b 로 출력한다.

 

 

 

 

반응형

+ Recent posts