[백준알고리즘/기본 수학 1단계] 2869번 문제 : 달팽이는 올라가고 싶다(자바/JAVA)

안녕하세요

백준 알고리즘 단계별로 풀어보기 8단계 2869번 문제 달팽이는 올라가고 싶다를 풀어봤습니다

이 전에 풀었던 문제 1712번 손익분기점과 비슷한 문제로 그렇게 어렵지 않게 풀었습니다

제가 풀은 방법에 대해서 설명하겠습니다

 

---

문제 링크입니다

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

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

 

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 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)