[Java 자바] 백준 알고리즘 2869번 답 : 달팽이는 올라가고 싶다

https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

 

이 문제^^ 참 욕나온다.

 

사실 문제만 보면 while문 돌리면 되는 간단한 문제라고 생각하겠지만 이 문제의 함정은 "시간 제한"에 있다..ㅋ

0.15초 실환가^^

0.15초인데다가 입력 조건을 보면 숫자 범위가 10억이다..ㅋ

반복문 절대 불가.. 쓰면 무조건 시간 초과 뜬다..

무적권 수식 하나로 마무리 해야한다..

 

 

일단 처음에 짜서 통과한 코드다!

 

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

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 res = (int)Math.ceil((double)(V-A)/(A-B));

        System.out.println(res+1);
    }
}

 

어떤 원리냐면,,

하루동안 A만큼 올라가고 B만큼 떨어지니까 (A-B)씩 계산하면 되는데,

이때 주의할 점이 A만큼 올라갔을 때 정상에 도달할 수 있으면 거기서 끝내야한다는 것이다.

그럼 이 문제에서 핵심은 마지막에 A를 올라가면 정상에 올라가서 끝낼 수 있느냐, 없느냐를 따지는 것이다.

 

V에서 A를 뺀 값을 A-B로 나누게되면 ? 만약에 나누어 떨어지면 딱 A만큼만 더 올라가면 된다는 뜻이니까 몫+1을 해주면 되고

나누어 떨어지지 않는다면 A만큼 올라간 것보다 좀 더 올라가야한다는 뜻이므로 무조건 올림해주면 된다. 그 후에 올림해준 값+1 !

 

근데 여기서 Math.ceil을 안쓰고 (V-A) % (A-B) 가 0인지 확인하는 코드 넣으니까,, 바로 시간초과가 떴다.. 허허 .. 

 

위의 설명을 영상으로도 제작해봤다! 혹시라도 위의 설명이 이해가 안되시면 아래 영상을 보시는걸 추천한다!

 

https://youtu.be/FiR7NmEE8AY

 

다른 분들은 (V-B) / (A-B)로 짜셨던데.. 내가 아무리 머리를 굴려도 명쾌하게 이해가 되진 않는다.

추후.. 이해하면.. 이 부분에 대해서도 포스팅하겠다,,ㅠ