[백준] 2869번: 달팽이는 올라가고 싶다 | C++ 풀이

# 문제

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

 

 

 

---

 

# 풀이

아주 귀여운 문제지만 시간 제한을 신경써야 하는 문제다.

정답 코드부터 한 번 확인해보자.

 

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);	// 두 표준 입출력 동기화 해제
    
    int a, b, v;
    int day = 1;
    cin >> a >> b >> v;

    day += (v-a) / (a-b);
    if((v-a)%(a-b)) cout << day+1;
    else cout << day;
    return 0;
}

🐌 처음엔 아주 귀여운 문제라 생각하며 시간제한에 전혀 신경을 안 썼다.

그렇게 while문으로 풀어낸 결과는 시간초과...

 

 

 

살짝 당황했지만 침착하게 다른 풀이를 생각했다.

정상에 올라간 후에는 미끄러지지 않는다는 게 포인트 같았고 그 부분에 집중해서 코드를 구현했다.

 

 

 

우선 달팽이가 나무 막대를 올라가는데는 두 가지 경우가 있다고 생각했는데,

(1) a만큼 올라갔을 때 딱 v에 도착하는 경우, (2) a만큼 올라갔을 때 v를 지나치는 경우(물론 정상에서 멈춘다고 가정)다.

그림에서 확인할 수 있듯이 우리는 v가 아니라 v-a를 도착 목표로 잡으면 미끄러지는 b를 고려하지 않고도 정상 도착까지 며칠이 걸리는지 계산할 수 있다.

 

(1)번 예시 그림의 경우 (v-a) % (a-b)는 0, (v-a) / (a-b) = 3 이다.

우리는 day 1에서 출발하므로 (v-a) / (a-b) 값을 그대로 day에 더해 출력하면 원하는 값을 얻을 수 있다.

 

하지만 (2)번 예시 그림처럼 (v-a) % (a-b)가 1, (v-a) / (a-b) = 1인 경우에는

day 1에서 출발하더라도 (v-a) / (a-b)를 day에 더하고도 하루를 더 더해주어야 원하는 값을 얻을 수 있다는 것을 확인할 수 있다.

 

 

 

day += (v-a) / (a-b);
if((v-a)%(a-b)) cout << day+1;
else cout << day;

확인한대로 코드를 구성해 출력해주면 끝이다!

 

 

 

 

 

---

 

 

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