[Java | 백준 1193] 분수찾기

백준 1193 www.acmicpc.net/problem/1193

 

 

풀이

 

지그재그 순서로 지나간다는 것이 여기서 주의할 점이다. 

2번째 줄을 보면 1/2 → 2/1

3번째 줄을 보면 3/1 → 2/2 → 1/3

즉, 짝수 줄의 분자는 증가, 분모는 감소이고 홀수 줄은 그 반대이다. 그리고 같은 줄에서 분자 + 분모 의 값 = 줄번호 +1 은 동일하다. 

 

줄은 1씩 증가하므로 for문에서 입력된 값을 순차적으로 차감해준다. 이제 남은 값이 i 보다 작아졌다면 i 줄에 그 분수가 위치한다는 뜻이다.

여기서 i 줄이 홀수인지 짝수인지 판단하고 분자와 분모를 계산해준다. 

 

만약 짝수라면, 분자는 check % i 인 나머지 값(check)이 될 것이고, 분모는 i 번째 줄이니까 i+1-check 값이 될 것이다.

홀수 줄이라면 위의 분자 분모를 바뀌어 출력한다.

 

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int check = n;
        int denominator = 0;     //분모
        int numerator = 0;        //분자
        
        for (int i=1; i<=10000000; i++) {
            if(check<=i) {
                denominator = check;
                numerator = i-check+1;
 
                if(i%2==0)
                    System.out.println(denominator+"/"+numerator);
                else
                    System.out.println(numerator+"/"+denominator);
                
                break;
            } else check=check-i;
        }
 
        sc.close();
    }
 
}