[JAVA | 백준] #2869 달팽이는 올라가고 싶다 🐌🆙

📍 달팽이는 올라가고 싶다

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

 

 

 

A와 V는 최대 10억이므로 단순히 반복문을 돌리면 시간초과 난다. (시간제한 0.25초)

정상에 올라간 후에는 미끄러지지 않으므로 한 번 올라갔다는 가정하에 V-A를 한다.

int answer = (V-A);

 

 

 

그 뒤로는 올라갔다 내려가는 것의 반복이므로 (A-B)로 나눈다. (B<A)

int answer = (V-A) / (A-B);

 

 

 

최소한 하루는 올라가야 하는데 (1<=B<V)

V와 A가 같을 경우 answer는 0이 되어버린다. 따라서 +1을 해준다.

int answer = (V-A) / (A-B) + 1;

 

 

 

🎱 반례

여기까지 작성하면 테스트케이스는 통과되지만 틀린 코드이다.

// 반례
5 1 8

 

 

반례의 경우, 달팽이가 나무 막대를 모두 올라가기까지 실제로 이틀이 걸리지만,

현재 식 (V-A) / (A-B) + 1 로 계산해보면 출력값은 1이 나온다. (기댓값: 2)

따라서 (V-A) / (A-B) 가 나누어 떨어지지 않는 경우도 생각해야 한다.

if((V-A) % (A-B) != 0) answer += 1;

 

 

 

✨ 전체 코드 ✨

import java.util.Scanner;

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 answer = (V-A) / (A-B) + 1;
        if((V-A) % (A-B) != 0) answer += 1;
        System.out.println(answer);
    }
}

 

 

 

🌀 성능

• 메모리 : 14,116 KB
• 시간 : 124 ms