[백준알고리즘-JAVA]2869번 풀이(달팽이는 올라가고 싶다)

안녕하세요

인포돈 입니다.

백준 알고리즘 2869번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2869 (달팽이는 올라가고 싶다)

 

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

입력 예시

2 1 5

출력 예시

4

입력 예시

5 1 6

출력 예시

2

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		
		double[] day = new double[str.length];
		int ans = 0;
		
		for(int i = 0; i < day.length ; i ++) {
			day[i] = Double.parseDouble(str[i]);
		}
		
		ans = (int)Math.ceil(((day[2]-day[1])/(day[0]-day[1])));
		
		System.out.println(ans);
		
		}
		}

해당 알고리즘에 핵심은 바로 수학식입니다. 달팽이 알고리즘을 접했을 때 저희는 문제를 분석해야 합니다. 문제에서 궁금해하는 것은 바로 며칠이 걸리는지입니다. 그러면 그 며칠을 어떻게 구할까요? 아래 STEP으로 차근차근 알려드리겠습니다.

 

STEP을 밟기 전 간략히 해당 알고리즘의 흐름도를 작성해보겠습니다.

입력받기 -> 받은 입력을 통해 day(며칠이 걸리는지) 구하기 -> 출력

 

간단하죠? 저기 있는 day식만 잘 도출한다면, 이번 문제는 쉽게 풀 수 있는 문제입니다. 자 STEP으로 가봅시다.

 

---

STEP1 며칠이 걸리는지 식 파헤치기

일단 며칠이 걸리는지를 day라는 변수라고 생각해 볼게요.

 

또한 문제에서 주어진 A = 달팽이가 낮에 올라갈 수 있는 거리 B = 달팽이가 잠을 자는 동안 미끄러지는 거리

V = 올라가야 하는 거리

 

이렇게 주어져있다는 것을 상기하세요

 

저희는 항상 주어진 예시를 잘 활용해야 합니다. 왜냐면, 더욱 가시적으로 볼 수 있고 쉽게 풀이할 수 있다는 장점이 있죠. 그 대신 너무 예시에 의존하다 보면, 다른 반례를 찾기 힘들어질 수 있다는 점 알아두세요~!

 

다시 본론으로 와서 저희가 사용할 예시는 2 1 5라고 생각해 봅시다.

 

자 하루 동안 달팽이의 거리를 아래처럼 생각해보죠

	현재위치	낮	밤
1일차	0	2	1
2일차	1	3	2
3일차	2	4	3
4일차	3	5

4일 차 낮에 목표지점에 도달하게 됩니다. 이것을 식으로 어떻게 표현해야 할까요?

 

V = A*day - B*(day-1) 이렇게 생각해볼 수 있죠.  왜 B는 (day-1)일까요? 

 

간단합니다. 저곳을 day라고 한다면, 방금 저희가 풀었던 예시에서 목표지점은 5일 차에 도달하게 됩니다. 

 

쉽게 말하면, 하루 도중에도 목표지점에 도달하면 바로 그 일수를 알면 된다는 말입니다.

 

좀 더 쉽게 보려면 역시 예시를 대입해보시면 됩니다. 

 

(B 뒤를 day로 생각한 경우)

5 = 2*day - 1*day  => 5 = day 즉, 5일이 거리게 됩니다. 표에서 보았듯이 저희는 4일 차에 목표에 도달했지만, 해당 식은 5일에 도착한다는 모순이 생깁니다. 이러한 모순을 없애주기 위해서 밤 B는 다음날에 미 끌어내려진다고 생각하시면 됩니다.

 

즉 1일 차 B만큼 떨어진다.(땅이어서 떨어질 곳이 없다.) A만큼 올라간다.

2일 차 B만큼 떨어진다. A만큼 올라간다.

 

이런 식으로 생각해주시면 됩니다.

 

그럼 이제 day의 식을 풀면 아래와 같습니다.

V = A*day - B*(day-1)
V = Aday - Bday + B
V-B = (A-B)day
(V-B)/(A-B) = day

 

---

STEP2 식에 숨어있는 함정 파헤치기

해당식을 그대로 답에 넣어주면, 문제가 생기게 됩니다.

 

2번째 예시 5 1 6을 해당 식으로 계산하면, 실수가 나오게 되죠. 5/4 = 1.25 이런 부분을 처리해 주어야겠죠.

 

바로 올림을 사용해서 해당 함정을 쉽게 해결할 수 있습니다.

 

Math의 간단한 메서드

 

Math.ceil(x) : x값 올림

Math.floor(x) : x값 버림

Math.round(x) : x값 반올림

 

앞서 답이 4 이렇게 정수로 나올 경우 올림 버림이 되지 않습니다. 해당 메서드를 돌려도 그대로 4의 값이 나오죠.

 

이런 식으로 해당 알고리즘을 풀어나가시면 됩니다.

 

---

다른 분들의 코드를 둘러보던 중 흥미로운 식을 발견해서 추가해서 올려봅니다.

 

day를 int day = (v-b-1)/(a-b)+1; 이런 식으로 정의하여 저처럼 추가의 Math객체를 안 불러도 되는 코드가 있더라고요. 참고하시면 좋을 것 같습니다~