[java] 백준 알고리즘 1193번 분수찾기 풀이

표를 보면 0행과 0열의 숫자가 올라갈수록 분수가 몇번째인지 규칙이 있다.

대각선으로 오르락 내리락하는 걸 볼 수 있는데,

열쪽에서 행쪽으로 대각선으로 내려오면 다음 분수는 바로 행의 아래부터 시작해서 열쪽으로 올라가는 형태다.

행쪽에서 대각선으로 열쪽으로 올라가면 다음 분수는 열의 바로 오른쪽부터 시작하는 형태다.

등차수열로 올라가는 수와 +1을 반복하면서 분수가 몇번째인지 기록하게 된다.

행이 홀수번째면 +1, 행이 짝수번째면 등차가 4로 올라가는 숫자의 합이다.

그에 맞춰 열도 행이 홀수번째면 등차가 4로 올라가는 숫자의 합이고 짝수번째면 +1이 된다.

*****

그래서 입력된 숫자가 행과 열의 사이에 있다는 걸 알게된 순간 break를 걸어 

분자와 분모를 찾아준다.

public class Baekjoon1193 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int x = Integer.parseInt(st.nextToken());
        
        int bunza = 1;
        int bunmo = 1;
        
        int row = 2; // 행 
        int rowOrder = 1; // 해당 행의 분수가 몇번째인가
        int columnOrder = 1; // 해당 열의 분수가 몇번째인가
        int rowCommonDiff = 2; // 행의 숫자가 커질수록 올라가는 등차
        int columnCommonDiff = 4; // 열의 숫자가 커질수록 올라가는 등차
        
        if(x > 1){
            
            while(true){
                if(row%2 == 0){
                    rowOrder += rowCommonDiff;
                    rowCommonDiff += 4;
                    
                    columnOrder += 1;
                    if(columnOrder <= x && x <= rowOrder){
                        break;
                    }
                }else{
                    rowOrder += 1;
                    
                    columnOrder += columnCommonDiff;
                    columnCommonDiff += 4;
                    
                    if(rowOrder <= x  && x <= columnOrder){
                        break;
                    }                
                }
                
                row++;
            }
            
            /* 기입한 숫자와 0열쪽의 번째수를 다루어주면 분자와 분모를 구할 수 있다 */
            bunza = row;
            if(rowOrder > columnOrder){
                bunza -= (rowOrder - x); 
                bunmo += rowOrder - x;
            }else{
                bunza -= (x - rowOrder);
                bunmo += x - rowOrder;
            }
        }    
        bw.write(String.valueOf(bunza) + "/" + String.valueOf(bunmo));
        bw.flush();
    }
 
}