[백준 2869] 달팽이는 올라가고 싶다 - Java

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

 

---

❓
알고리즘은 금방 해결했는데 시간 초과에서 고민했던 문제.
사실 처음엔 정상에 올라간 후에는 미끄러지지 않는다. 라는 조건을 고려하지 않아 원하는 값이 나오지 않았었다. 문제는 잘 읽어야 한다...
해당 부분을 해결하니 시간 초과 문제가 발생함.
일일이 값을 더하고 빼서 그런 것 같다는 생각이 들었는데, 이를 어떻게 해결해야 할지 도저히 감이 잡히지 않았다.

❗
결국 다른 사람의 풀이를 보고 문제를 풀었다.
어떻게 저런 방법을 생각하시는 걸까...

 

✨ 참고

https://st-lab.tistory.com/75

[백준] 2869번 : 달팽이는 올라가고 싶다 - JAVA [자바]

---

 

풀이1

• ★ 전체 높이에서 미끄러지는 길이를 뺀다. (V-B)
• 올라가는 길이와 미끄러지는 길이의 차를 구한다. (A-B)
• V-B와 A-B를 나눈 몫은 달팽이가 나무막대를 올라가는 데 걸리는 일수
• V-B와 A-B를 나눈 나머지가 0이 아닌 경우 달팽이는 하루를 더 올라간다.

 

처음엔 왜 V에서 B를 빼나 싶어서 헤맸다.

조건은 이해했는데, 왜 B를 빼는 거지? A를 뺄 순 없나? (A를 빼도 된다. - 풀이2에서 설명)

 

정상에서 미끄러지지 않는다는 조건이 없다면 전체 높이를 '하루동안 실질적으로 올라가는 높이'로 간편하게 나눠버리면 된다.

V / (A - B)

하지만 그러한 조건이 있기 때문에 완등 시 더이상 미끄러져도, 날짜를 세도 안 된다. 위와 같은 식은 불가능하다.

 

결국 전체 높이 V에서 미끄러지는 길이 B를 빼는 이유는 달팽이가 완등 후 미끄러졌다는 전제 하에 문제를 풀기 위함이다.

V-B는 달팽이가 완등 후 미끄러졌을 때의 위치인 것이다. 따라서 이를 달팽이의 실질적 이동 거리인 A-B로 나누면 달팽이가 나무 막대를 오르는 데 걸린 시간을 구할 수 있다.

(V - B) / (A - B)

이때 V-B와 A-B를 나눈 나머지가 0이라면 달팽이가 꼭대기를 찍은 후 미끄러졌다는 얘기이므로 굳이 몫에 1을 더해줄 필요가 없다.

하지만 그 나머지가 0이 아니라면 올라야 할 나무 막대가 남았다는 얘기이므로 1일을 추가해줘야 한다.

 

코드

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

public class Snail2869 {

	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 days = (v-b) / (a-b);
		
		if ( (v-b) % (a-b) != 0 ) {
			days++;
		}
		
		System.out.println(days);
	}

}

 

---

 

풀이2

풀이1과 동일하지만 전체 나무 막대 길이에서 '미끄러지는 길이' 대신 '올라가는 길이'를 뺀 방법이다.

 

쉽게 예제 입력 3의 경우로 생각해보면, 달팽이는 1000000000미터 길이의 나무 막대를 하루 100미터 올라가고 99미터 미끄러진다.

하루동안 실질적으로 올라가는 높이는 1미터지만, 남아있는 나무 막대 길이가 100미터 이하라면 달팽이는 한번에 100미터를 올라가 더이상 미끄러지지 않기 때문에 날짜 세기는 그대로 끝난다.

 

• 전체 길이에서 달팽이가 오르는 길이인 100미터를 뺀다.
• 그 값을 달팽이가 실질적으로 오르는 길이인 1미터로 나눈 후, 몫+1
  • +1을 하는 이유는 초반에 뺀 100미터를 달팽이가 다시 올라야 하기 때문이다.
• V-A를 A-B로 나눈 나머지가 0이 아니라면 추가로 +1

 

코드

큰 변경사항 없이 풀이1의 코드에서 아래 부분만 바꾸면 된다.

		int days = (v-a) / (a-b) + 1;
		
		if ( (v-a) % (a-b) != 0 ) {
			days++;
		}

 

---

 

풀이3 (시간 초과)

• 수학적 풀이 대신 반복문 처리

 

코드

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

public class Snail2869 {

	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 height = 0;
		int days = 0;
		
		while (height < v) {
			days++;
			
			height += a;
			if (height >= v)
				break;
			
			height -= b;
		}
		
		System.out.println(days);
	}

}

 

 

반복문을 수학적 풀이로 간결하게 표현할 방법은 사실 거의 떠올리지 못했다.

사고력을 키우려면 어떻게 해야할까?

일단 꾸준히 문제를 풀어보고, 다른 사람들의 코드도 많이 참고해야겠다.

같은 결과를 내더라도 최적의 알고리즘을 이용하는 방법에 대해 계속 고민해봐야겠다.