백준 1193 분수찾기

<1193번 분수 찾기>

문제 링크 : https://www.acmicpc.net/problem/1193

요즘 알고리즘 문제 푸느라 시간을 보내고 있는데...역시 실력은 꾸준함만이 진리인듯하다.

일단 이 문제는 아래 그림과 같다. 

문제를 읽어보면 일단 순서는 지그재그 형태로 나아간다. 

(그림 1)

예제를 보면 14번째에 있는 분수를 찾아달라고 할 때 위에 그림을 보면 14번째에 2/4가 적혀있다. 그래서 출력은 2/4를 출력해야한다. 맨 처음 문제가 이해가 안되서 한참 걸렸다. 하지만 저 그림보면 금방 이해될듯 하다. 
지금 현재 우리의 고개를 왼쪽으로 45도 정도 기울여주자! 그러면 밑에 있는 그림2처럼 보일것이다.

(그림 2)

일단 분자=up , 분모=down 이라는 변수로 치환하였다. (변수는 내가 편한대로 직관적으로 정했음)

일단 이 문제를 찾기 위해서 규칙을 찾는것이 우선이다 싶었다. 그래서 아래부터는 규칙을 찾기 위한 노력이다. 

(그림 3)

그림 3에서는 첫번째 홀수인 번호인 1번째 루프를 돌 때 분자가 1부터 시작합니다. 

그리고 두번째 짝수인 2는 분모가 2로 시작합니다. 

이런식으로 계속 보면 마지막 다섯번째는 홀수이기 때문에 숫자 5가 분자에 위치하고 있습니다. 

(그림 4 )

그림 4에서는 짝수일 때에는 분자가 점점 1씩 증가하고, 분모는 점점 1씩 감소합니다. 

홀수 일 때에는 그 반대입니다. (분자 -1, 분모 +1)

그래서 변수 n과 입력한 숫자 num이 같을 때 분수를 출력하고 프로그램이 끝나는 알고리즘을 생각했습니다. 

아래는 소스입니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    Main() throws IOException {
        int num = scan();
        whatFraction(num);
    }
 
    int scan() throws IOException{
        //Scanner sc = new Scanner(System.in);
        //return sc.nextInt();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num=Integer.parseInt(br.readLine());
        return num;
    }
 
    static void whatFraction(int num) {
        int up = 0; //분자
        int down = 0; //분모
        int n = 0; //몇번째 숫자인지 확인
        Boolean findFraction = false;
        for (int i = 1; i <= num; i++) {
            for (int j = 0; j < i; j++) {
                if (i % 2 != 0) {//홀수 일 때
                    down = j + 1;
                    up = i - j;
                } else {
                    //짝수 일 때
                    up = j + 1;
                    down = i - j;
                }
                String txt = up + "/" + down;
                n++;
                if (n == num) {//입력된 순서와 n이 같으면 출력
                    System.out.print(txt);
                    findFraction=true;
                    break;
                }
            }
 
            if(findFraction)
            {//분수를 찾았으면 바깥쪽 for문도 break 해준다.
                break;
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        new Main();
    }
}
 

맞추고 나서 백준에서 다른 사람 소스 보니깐 저보다 훨씬 간단하게 푼 사람도 있더군요. 아쉽게도 다른 사람 소스를 맘대로 퍼올수 없어서 다룰순 없겠지만 제 소스에 대해 더 효율적으로 푸는 방법 있으신 분은 같이 토론해요! 

(시간복잡도가 O(N^2) 같네요. for문이 두번이니..다른 사람 소스는  O(n)으로 더 빠르게 처리 하더군요.ㅠㅠ)