안녕하세요
백준 알고리즘 단계별로 풀어보기 8단계 2869번 문제 달팽이는 올라가고 싶다를 풀어봤습니다
이 전에 풀었던 문제 1712번 손익분기점과 비슷한 문제로 그렇게 어렵지 않게 풀었습니다
제가 풀은 방법에 대해서 설명하겠습니다
문제 링크입니다
https://www.acmicpc.net/problem/2869
2869번: 달팽이는 올라가고 싶다
첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)
www.acmicpc.net
문제
땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)
출력
첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.
문제 풀이
문제를 푸는 방법은 먼저 공식을 파악해야합니다
하루에 달팽이가 올라가는 높이는 A - B입니다
하지만 정상에 오르는 순간 달팽이는 더이상 내려가지 않으므로 B만큼 뺄 필요가 없게됩니다
이 점에 유의해서 푸시면 어렵지 않게 풀 수 있습니다
첫 번째 방법
첫 번째 방법은 약간 서툴게 풀었습니다
double을 선언하여 Math.Ceil을 사용하여 문제를 풀었습니다
마지막 날의 정상에 오른만큼은 빼줘야하므로 (V - A)를 해줍니다
이어서 하루에 오르는 높이 (A - B)를 한 후 (V - A) / (A - B)를 하여 몇 일이 걸리는지 구합니다
소수점이 나오는 경우 Ceil을 하여 올림처리를 해줍니다
이어서 +1을 더해줍니다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// BufferedReader 및 A, B, V 변수 선언
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
double A = Integer.parseInt(st.nextToken());
double B = Integer.parseInt(st.nextToken());
double V = Integer.parseInt(st.nextToken());
// 날짜를 계산
int count = (int) Math.ceil((V - A) / (A - B)) + 1;
// 결과 출력
System.out.print(count);
}
}
두 번째 방법
먼저 내려가는 양만큼 정상높이에서 빼줍니다
이어서 하루 올라가는 높이만큼을 나눠줍니다
0으로 나누어떨어진다면 딱 알맞게 정상에 도착하게됩니다
하지만 0으로 나누어떨어지지 않으면 1일을 더해줍니다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main2 {
public static void main(String[] args) throws IOException {
// BufferedReader 및 A, B, V 변수 선언
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 count = (V - B) / (A - B);
// 0으로 나누어 떨어지지 않으면 +1을 해줍니다
if((V - B) % (A - B) != 0)
count++;
// 결과 출력
System.out.print(count);
}
}
여기까지 두 가지 방법으로 풀어봤습니다
이제 속도비교를 해보겠습니다
속도 비교
두 개를 비교했을 때 시간의 차이는 없습니다
하지만 2번 방식이 메모리가 약간 적게 드는 것을 볼 수 있습니다
이상 백준 알고리즘 2869번 달팽이는 올라가고 싶다를 풀은 내용이었습니다
다음 문제 : 2021.05.25 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 1단계] 10250번 문제 : ACM 호텔
이전 문제 : 2021.05.24 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 1단계] 1193번 문제 : 분수찾기(자바/JAVA)
'알고리즘 > 알고리즘JAVA' 카테고리의 다른 글
[백준알고리즘/기본 수학 1단계] 2775번 문제 : 부녀회장이 될테야 (0) | 2021.05.25 |
---|---|
[백준알고리즘/기본 수학 1단계] 10250번 문제 : ACM 호텔 (0) | 2021.05.25 |
[백준알고리즘/기본 수학 1단계] 1193번 문제 : 분수찾기(자바/JAVA) (0) | 2021.05.24 |
[백준알고리즘/기본 수학 1단계] 2292번 문제 : 벌집(자바/JAVA) (0) | 2021.05.22 |
[백준알고리즘/기본 수학 1단계] 1712번 문제 : 손익분기점(자바/JAVA) (0) | 2021.05.22 |