728x90
백준 2869번 달팽이는 올라가고 싶다
문제 설명
땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)
출력
첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.
나의 문제 풀이 코드
import java.io.*;
public class bj2869 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
// 마지막 날에는 A만큼 올라가지 않으므로 V - A로 나누어 올림한 값을 출력합니다.
int day = (int) Math.ceil((double) (V - A) / (A - B)) + 1;
bw.write(String.valueOf(day));
bw.flush();
}
}
문제 풀이 코멘트
처음 이 문제를 보았을 땐 생각보다 어렵지 않은데? 라는 생각을 하며 아래의 코드로 풀었습니다.
import java.io.*;
public class bj2869 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
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 day = 0;
int sum = 0;
while (sum < V){
day++;
sum += A;
if (sum >= V)
break;
sum -= B;
}
bw.write(String.valueOf(day));
bw.flush();
}
}
하지만 이 코드를 제출하면 시간 초과가 발생했습니다. 문제는 똑같이 풀리지만 메서드를 어디서 어떻게 사용하느냐에 따라 시간 복잡도가 달라집니다.
정답 풀이에서 사용한 Math.ceil을 설명하자면 다음과 같습니다.
Math.ceil 함수 :
- (V - A)는 나무 막대의 총 높이에서 첫 번째 날에 올라가는 높이 A를 뺀 값입니다. 이는 나무 막대에서 첫 번째 날 이후에 올라가야 하는 높이를 나타냅니다.
- (A - B)는 하루에 올라가는 높이와 밤에 미끄러지는 높이의 차이입니다. 이 값은 하루에 얼마나 높이를 올라갈 수 있는지를 나타냅니다.
- (V - A) / (A - B)는 나무 막대의 총 높이를 첫 번째 날부터 하루에 올라갈 수 있는 높이로 나눈 것으로, 결과값은 첫 번째 날 이후 몇 일이 걸리는지를 나타냅니다.
- Math.ceil 함수는 이 값을 올림한 정수로 변환합니다. 즉, 소수점 이하가 존재하는 경우에도 다음 날로 올림하여 최소한의 일수를 구합니다.
- 마지막으로 + 1을 더하는 이유는 첫 번째 날을 포함하기 위함입니다.
결과적으로, day 변수에는 나무 막대를 모두 올라가는데 필요한 최소한의 날짜가 저장되며, 이 값을 출력합니다. 이 코드는 반복문 없이 Math.ceil 함수를 활용하여 간결하고 빠르게 문제를 해결이 가능합니다.
728x90
'공log > [P&B]' 카테고리의 다른 글
[P&B] #68 BAEKJOON 2292 (0) | 2023.09.18 |
---|---|
[P&B] #67 BAEKJOON 2903 (0) | 2023.09.18 |
[P&B] #65 BAEKJOON 11005 (0) | 2023.09.18 |
[P&B] #64 BAEKJOON 2475 (0) | 2023.09.18 |
[P&B] #63 BAEKJOON 25206 (0) | 2023.09.17 |