[백준 JAVA] 2869 - 달팽이는 올라가고 싶다

시간초과에 대해 생각해 보라는 재밌는 문제였다.

 

3년전에 푼 기억이 있지만, 너무 오래되어서 까먹었다,, 처음 한다는 느낌으로 다시 이 문제를 접하게 되었다.

 

여기서 중요한 점은 시간 제한이 0.25초인 점이다.

 

그래서 나는 혹시 몰라 틀린다는 마인드로 시간제한을 생각하지 않은 로직을 짜보았다.

while (num <= v)
for 문 돌 때 마다, num + a, num - b
그런데 제한 시간이 0,25초라 되는지 모르겠음.

 

import java.io.*;
import java.util.*;


public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        int num = 0;
        int count = 0;

        while (num <= v) {

            num += a;

            if (num >= v) {
                count++;
                break;
            }
            num -= b;

            count++;
        }

        System.out.println(count);
    }
}

 

혹시몰라 한번 이렇게 만들고 제출해 보았다.

 

역시나,,

 

그래서 다른 방법을 찾던 중,, 도저히 생각이 나지 않아서 결국 풀이법 구조만 다른 글에서 참고를 했다.

보니깐, 시간제한이 0.25 초기 때문에, for문도 안되니깐 변숫값으로 입력 받는 구조를 해야 된다고 보았다!

그래서 내린 결론이,,

 

[최종코드]

package BaekJoon.step_8.Bronze_2869;
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        int count = (v - b) / (a - b);

        if ((v - b) % (a - b) != 0)
            count++;

        System.out.println(count);
    }
}

 

잘된다!

 

배운 점

나는 안 풀리면 섣불리 정답 코드를 보는 습관이 있다. 이런 걸 조금 줄여야겠다고 생각이 들었다.

그리고, 시간제한이 짧다면, 이런 식으로 시간 복잡도를 구하는 방식으로 접근해야겠다고 생각했다!