출처: 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