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

 

---

1) 처음 푼 방법 (반복문 사용)

● 시간제한을 보지 않고 반복문을 사용했더니 시간 초과가 났다.

● 입력값에 대한 출력 자체는 맞게 나오지만 시간이 초과돼기 때문에 수학 공식을 만들어서 풀어야한다.

 

import java.util.Scanner;

public class Baek_2869 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();       // 낮에 올라갈 수 있는 a미터 변수
        int b = sc.nextInt();       // 밤에 미끄러지는 b미터 변수
        int v = sc.nextInt();       // 나무의 높이 변수
        int sum = 0;                // 달팽이가 올라가고 미끄러진 후 다음날까지 자신의 위치미터 변수
        int count = 1;              // 달팽이가 나무를 다 오르는데 걸리는 날짜 변수
        boolean day = true;         // 낮인지 밤인지 확인하는 변수

        while (true) {
            // 현재 낮이라면,
            if (day == true) {
                sum += a;        // 올라간 달팽이의 위치
                if (sum >= v) {
                    System.out.println(count);
                    break;
                }
                day = false;
            }

            // 현재 밤이라면,
            if (day == false) {
                sum -= b;       //  그날 미끄진 이후 달팽이의 위치

                if(v == sum) {
                    System.out.println(count);
                    break;
                } else {
                    day = true;
                }
            }

            count++;
        }
    }
}

 

2) 수학공식을 사용한 풀이

● Scanner > Buffered로 바꿔주고 공식을 세워 풀었다.

● 문제의 핵심은 달팽이가 정상을 찍은 뒤 미끄러지지 않는 것인데, 때문에 단순하게 v / (a-b) 를 해버리면 오답이다.

  예) 입력이 2 1 5 일 때, v / (a-b)를 한다면 출력 값은 5가 나오지만 테스트케이스 출력 값은 4가 나온다. (오답)

● 자세한 것은 주석을 참조

 

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

public class Baek_2869_buffered {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

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

        /* 처음부터 높이에서 a만큼 올라가는 길이를 빼준 뒤 a-b로 나눠 떨어지는 경우와 안 나눠 떨어지는 경우를 구분한다.
           만약 a-b로 나눠 떨어진다면 달팽이는 a를 올라가기 위해 하루 더 소요 즉, 1일을 더해주면 될 것이고,
           만약 a-b로 나눠 떨어지지 않는다면 달팽이는 a 만큼 올라가도 나눠 떨어지지 않은 나머지 길이를 올라가야 할
           것이기 때문에 나머지 길이를 올라가는데 하루, a만큼 올라가는데 하루 즉, 이틀을 더해줘야 한다.
        */ 

        int day = (int)Math.ceil((double)(v - a) / (a - b));
        
        // 나눠 떨어졌다면 반올림 x > 출력 시 +1 더해주기.
        // 나눠 떨어지지 않았다면, 반올림으로 +1 될 것이고, 출력 때 다시 +1 더해주면 됨.
        System.out.println(day + 1);
    }
}