백준 1193번 분수찾기 자바로 풀어 본 짧은 글

1193번 분수찾기 문제

생각

처음 시도한 방법 : 칸을 생각하지 않고 분자와 분모의 규칙성을 찾아내서 

1 - 1 - 2 - 3 - 2 - 1 - 1 - 2 - 3 - 4 - 5 - 4 - 3 - 2 – 1 - 1– 2 – 3 – 4 – 5 – 6 – 7 – 6 – 5 – 4 – 3 – 2 - 1

분자 A 규칙 : 1 + 2의 기준 패턴으로 계속 더해졌다 빼졌다 반복

1 – 2 – 1 – 1 – 2 – 3 – 4 – 3 – 2 – 1 – 1 – 2 – 3 – 4 – 5 – 6 – 5 – 4 – 3 – 2 - 1

분모 규칙 : 0 + 2의 기준 패턴으로 계속 더해졌다 빼졌다 반복

이러한 패턴을  알게 돼서 구현만 하면 될줄 알았는데 나중에 확인해보니 시간제한이 0.5초였다.

또 내가 수학적 생각을 안하고 무대포로 풀 생각만 했구나 싶었다.

결과적으로 저렇게 연산을 했을 때 시간이 부족해서 필히 문제가 생겼을 것이다.

아무리 생각해도 정확한 정답이 나오지 않아 결국 다른 분들의 풀이를 봤다.

-------

hint

이걸 보면서 규칙성 확인

 

-------

Solution

import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        
        int a = 0;
        int count = 1;
        int b = 0;
        int tmp = 0;
        int mother, child;
        
        while(true) {
            if( a >= n ) {
                b = a - n - 1;
                
                mother = n - tmp;
                child = count - mother;
                if(child < 0) {
                    child *= -1;
                }
                
                child = count - mother;
                if(count % 2 == 1) {
                    System.out.println(mother + "/" + child);
                }
                else {
                    System.out.println(child + "/" + mother);
                }
                break;
            }
            
            tmp = a;
            a += count;
            count++;
        }
    }
}
 
// 2 3 4  5  6  7  8
//1 3 6 10 15 21 28 36

실행시간 - 224ms

위의 hint그림 처럼 대각선 기준으로 정방향 역방향으로 1부터 순차증가가 된다.
이 부분을 체크해서 각 대각라인 별 갯수가 1 - 3 - 6 - 10 - 15 - 21 순으로 증가하는데,
a(0) = a + 대각라인 으로 총 갯수를 파악 가능하며, 
child / mother라 했을 때 mother = n - tmp로 해당 번호의 순번, 즉 분자나 분모의 값 하나를 구할 수 있고
이후 count - mother를 통해 다른 분자나 분모의 값을 구할 수 있다.
count - mother가 가능한 이유는 각 대각라인 순번별로 2부터 시작해 합이 1씩 증가한다. 그 합은 child + mother 이다.

---
수학 문제는 난이도가 쉽게 나와도 정말 풀기 어려운 듯 하다 최적화를 떠나서 구현 자체가 너무 힘듦
이후에도 해당 문제는 계속 들여다볼 것 같다.