[백준] 1193 : 분수찾기 JAVA 풀이

 

분명 카테고리는 '기본' 수학1인데 나에겐 너무 어려웠다..

메모장을 켜놓고 정리해가면서 겨우 규칙을 찾았다 ㅜㅜ

 

파란색이 대각선이 짝수번째일 때, 빨간색이 대각선이 홀수번째일 때이다.

 

위 그림을 보면 

대각선이 짝수번째일 때는 분자는 커지고, 분모는 작아지며

홀수번째일 때는 이와 반대라는 것을 알 수 있다.

 

그리고 다음과 같이 코드를 작성할 순서를 정했다.

1. 원하는 분수 번호를 입력받는다.
2. 입력받은 번호가 몇 번째 대각선에 있는지 찾는다.
3. 입력받은 번호가 그 대각선에서 몇 번째에 있는지 찾는다.
4. 대각선의 진행방향에 따라 원하는 분수의 값을 찾는다.

 

변수는 세 개를 사용했다.

1. 찾아야 하는 분수의 번호 X
2. 몇 번째 대각선인지를 의미하는 line
3. 그 대각선까지 존재하는 총 칸의 개수 cnt

이 변수들로 대각선이 짝수번째일 때와 홀수번째일 때 값이 변하는 것을 어떻게 표현할지 고민해보았다.

값이 변하는 범위가 결국 1과 line 사이라는 것과

찾고자 하는 분수가 line번째 대각선에서 몇번째에 위치하는지를 나타내려고 하다보니 수식을 찾을 수 있었다.

 

짝수번째의 경우에는

분자는 line - (cnt-X)인데 여기서 cnt-X가 그 대각선에서 몇번째에 위치하는지를 구하는 식이다.

X(분수번호)가 커질수록 cnt-X가 작아지니

짝수번째 대각선에서 분자가 점점 커지는 것을 line - (cnt - X) 로 나타냈다.

 

분모는 cnt - X + 1인데 , 위와 마찬가지로

X(분수번호)가 커질수록 cnt-X가 점점 작아지니 이렇게 나타냈다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public 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 line = 0; // 몇 번째 대각선인지
        int cnt = 0; // 그 대각선까지 전체 칸의 개수
        
        while(true){
            line++; // 대각선을 증가시킴
            cnt +=line; // 칸수를 증가시킴 (한 줄에 있는 칸 수 = 대각선의 번호)
            
            if(cnt>=X){ // 전체 칸 수가 X보다 커지면 
                if(line%2==0){ // 짝수번째 대각선이라면
                    System.out.printf("%d/%d",line-(cnt-X),cnt-X+1);
                }
                else{ // 홀수번째 대각선이라면
                    System.out.printf("%d/%d",cnt-X+1,line-(cnt-X));
                }
                break;
            }
        }
    }
}

이렇게 식을 도출하기까지 오래 고민했는데 풀고나니 코드 자체는 또 간단해서 서글퍼진다...