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

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

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());
        
        // 1 = v - a 하루를 빼뒀다.
        // 남은 나무 길이(v - a)를 하루(낮과 밤)동안 올라갈 수 있는 양(a - b)으로 나눠주고 더해줌.
        int days = 1 + ((v - a) / (a - b));
        // 만약 나눴을 때 나머지가 있다면 하루가 더 걸릴테니 +1
        if ((v - a) % (a - b) > 0) {
            days += 1;
        }
        // 아니라면 더할 필요 없이 출력
        System.out.print(days);
    }
}

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

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 result = 0;
        int count = 0;
        while(result < v) {
            count++;
            result += a;
            if (result >= v) {
                break;
            }
            result -= b;
        }
        System.out.print(count);
    }
}

처음에는 모든 수를 연산했다.

1. 달팽이가 오른 만큼 더해주고

2. 만약 총 오른 합이 나무의 길이보다 크거나 같다면 break로 탈출 아니라면 계속

3. 자는 동안 내려오는 만큼 빼주고

while문으로 반복했더니 테스트 케이스에 100 99 1000000000 가 있었는데

수가 커지면서 시간 초과가 일어났다..ㅋㅋㅋㅋ 다시 생각했다.

 

첫번째 풀이든 두번째 풀이든 공통점은

(그 동안 올라간 x미터 + 낮에 올라간 x미터) >= 나무길이

상황이라면 멈춰야 한다.

 

그래서 달팽이가 올라갈 수 있는 만큼 나무길이에서 빼주면서 하루를 미리 빼두었다. v - a.

그리고 남은 나무길이를 하루에 올라갈 수 있는 양을 나눠 더해주고

만약 나눴을 때 나머지가 발생한다면 +1, 아니라면 더할필요 없으니 출력