백준 알고리즘 1011 - Fly me to the Alpha Centauri

처음에는 이걸 어떻게 풀어야 하나 했다가 for문으로 계속 순회를 시켜야 겠다 싶었다.

1, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8

해보면 이런 규칙을 지니고 있다는 것을 알 수 있다.

그래서 loopCount를 만들어서 순회를 할때마다 1번씩 더 순회 하게 만들었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(bf.readLine());
        
        String string;
        StringTokenizer st;
        
        int x, y;
        
        for (int i = 0; i < testCase; i++) {
            string = bf.readLine();
            st = new StringTokenizer(string);
 
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            
            calculate(y - x);
        }
    }
    
    public static void calculate(int length) {
        
        int loopCount = 1;
        
        int odd  = 1;
        int even = 2;
        
        for (int i = 1; i < length+1;) {
            for (int j = 0; j < loopCount; j++) {
                if (length == i) {
                    System.out.println(odd);
                    return;
                }
                i++;
            }
            for (int j = 0; j < loopCount; j++) {
                if (length == i) {
                    System.out.println(even);
                    return;
                }
                i++;
            }
            loopCount++;
            odd+=2;
            even+=2;
        }
    }
}
 

결론은 백준에 제출했는데 시간초과로 틀려버리고 말았다.

그래서 이번에는 반대로 2, 4, 6, 8 씩 뺀 다음에 -값이 되면 마지막에 뺀값을 다시 더한 다음에

뺀값의 절반 보다 크면 뺀값, 작으면 뺀값 -1 을 출력 하도록 만들었다.

package baek1011;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(bf.readLine());
        
        String string;
        StringTokenizer st;
        
        int x, y;
        
        for (int i = 0; i < testCase; i++) {
            string = bf.readLine();
            st = new StringTokenizer(string);
 
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            
            calculate(y - x);
        }
    }
    
    public static void calculate(int length) {
        int minCount = 2;
        while (true) {
            length -= minCount;
            if (length <= 0) {
                length += minCount;
                
                if (length > minCount/2) {
                    System.out.println(minCount);
                    return;
                }else {
                    System.out.println(--minCount);
                    return;
                }
            }
            
            minCount += 2;
        }
    }
}

이걸로 통과를 했다.

중간에 변수를 뺴서 줄여서 84ms까지 단축을 시켰다.

처음에는 어찌 풀을까 싶었는데 잘 풀려서 다행이다.

https://www.acmicpc.net/problem/1011