TIL | [알고리즘] 달팽이는 올라가고 싶다(Java)

BOJ 달팽이는 올라가고 싶다(2869번)

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

예제 입력

1) 2 1 5
2) 5 1 6
3) 100 99 1000000000 

예제 출력

1) 4
2) 2
3) 999999901

THIKING

관건은 "정상에 올라간 후에는 미끄러지지 않는다" 부분인 것 같았다. 이게 아니라면 그낭 V / (A - B) 로 간단하게 풀 수 있기 때문이다.

나는 아래와 같이 풀었다.
1) V에 A를 빼서 day +1 을 한다
2) V - A 값을 A - B로 나눈 몫을 day에 더한다
3) 만약 나머지가 있다면 다시 day +1을 해준다

첫번째 풀이 - 시간 초과

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int A = sc.nextInt();    // up
        int B = sc.nextInt();    // down
        int V = sc.nextInt();    // height
        
        int day = (V - A) / (A - B) + 1;
        
        if ((V - A) % (A - B) != 0) {
            day++;
        }
        System.out.println(day);
    }
}

생각보다 빨리 끝났네 하고 위의 코드로 제출하니 바로 시간 초과가 떠버렸다. 그렇게 복잡한 코드도 아닌데 시간초과가 나서 다시 살펴보니 정답률이 29%인 것을 보고 많은 사람들이 시간초과가 났겠구사 하고 짐작을 했다.

알고리즘 스터디 팀원이 Scanner를 쓰면 시간 초과 될 가능성이 높다고 예전에 말해주신 적이 있어서 Scanner 대신 BufferedReader를 사용해서 다시 풀어보았다.

두번째 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
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());    // up
        int B = Integer.parseInt(st.nextToken());    // down
        int V = Integer.parseInt(st.nextToken());    // height
        
        int day = (V - A) / (A - B) + 1;
        
        if ((V - A) % (A - B) != 0) {
            day++;
        }
        System.out.println(day);
    }
}

배운 것

키보드 사용자 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

입력 한줄에 받기
br.readLine()

특정 문자열을 기준으로 나누기
StringTokenizer st = new StringTokenizer(s, " ");
// s 문자열을 공백을 기준으로 나눔