백준 2869번 문제 - 달팽이는 올라가고 싶다 풀이(자바)

처음 문제를 접했을 때는 바로 아래와 같이 코딩을 했었다.

 

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str);
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        int h = 0;
        int day = 1;

        while (true) {
            h += a;
            if(h >= v) {
                break;
            }
            h -= b;
            day++;
        }
        System.out.println(day);
        br.close();
    }
}

하지만 이렇게 코딩을 하면 결과에 '시간 초과'라고 뜨게 된다.

이는 시간 복잡도가 너무 높아 문제의 제한 조건을 만족하지 못하기 때문이다.

특히 v(나무 막대 높이)값이 커질수록 반복문을 많이 실행해야 하므로 비효율적이다.

 

해당 문제는 보다 수학적으로 해결을 해야한다.

달팽이는 하루에 a만큼 올라가고 b만큼 내려오기 때문에 실질적으로 하루에 이동하는 높이는 (a - b)이다.

그리고 달팽이는 마지막 날에는 나무 막대를 올라가기는 하지만 내려오지는 않는다.

때문에 실질적으로 총 올라가야하는 높이는 (v - b)이다.

 

v = (a - b) + (a - b) + ... + a

↓

v - b = (a - b) + (a - b) + ... + (a - b)

 

 

그렇다면, (v - b) / (a - b)를 해주면

달팽이가 올라가는데 며칠이 걸리는지 알 수 있을 것이다.

하지만, 실제 수를 대입하다 보면 해당 식이 딱 맞아 떨어지는 경우도 있지만

나머지가 남는 경우도 생길텐데 그럴 경우에는 하루가 더 걸린다는 소리다.

 

if문을 써서 두 가지 경우로 나누어 코드를 짤 수도 있겠지만

애초에 마지막 하루를 마지막에 더해서 날짜를 계산한다고 치면

 

(v - b) / (a - b) + 1 

 

하지만 이렇게 되면 딱 맞아 떨어지는 경우에는 하루가 더 생기므로

 

(v - b - 1) / (a - b) + 1 

 

라고 해서 강제로 나머지가 생기게 만들고 하루를 더해주는 식으로 만들어준다.

이렇게 하면 아주 간결하게 코드를 끝낼 수 있다.

 

완성된 코드를 보자.

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str);
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        int day = (v - b - 1)/(a - b) + 1;
        System.out.println(day);
        br.close();
    }
}

이런 식으로 아주 간결하게 문제를 풀어낼 수 있다.