백준/백준 단계별 문제풀이

백준 2869번 (C++)

FDEE 2020. 8. 25. 13:09

www.acmicpc.net/problem/2869

 

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

문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 ��

www.acmicpc.net

 

<답안>

#include <iostream>

using namespace std;

int main()

{

    int a,b,v;

    int days = 0;

    int term;

    cin>>a>>b>>v;

    term = a-b;

    if((v-a)%term == 0)

        days = (v-a) / term + 1;

    else

        days = (v-a) / term + 2;

    cout<<days;

    

    return 0;

}

 

<설명>

위로, 아래로, 위로, 아래로 반복하다가 위로 올라가는 순간 v와 같거나 넘어버리면 되는 상태이다

그러면, 하루를 기준으로 위로 아래로를 더하여 하루동안 올라가는 양을 구한다음에

하루동안 올라가는 양 * (days - 1) + 올라가는양 >= 높이

이 때의 days를 구하면 된다

 

하루동안 올라가는 양 term은 a-b 이다

식 : term * days + a >= v 이다 정리를 하면

days >= (v-a) / term 이다

 

여기서 주의할 점은 두가지이다

구해진 days는 "도달하기 전까지의 일수" 이므로 최종값은 +1을 해야 한다

만약 나눈값이 1.5 라는 값이면 int형간의 나눗셈 결과값은 1이 될수밖에 없다

따라서 나누려는 v-a 값이 나누는 term의 배수인 경우 +1만 하면 되지만

배수가 아닌 경우는 소수점이 날아가기에 +1을 더해줘야 한다

 

최종적으로 days를 출력한다

 

※ 참고로 처음시도는 반복문으로 풀었지만 시간초과가  생겨 식을 구상하다가 푼 케이스이다

 

'백준 > 백준 단계별 문제풀이' 카테고리의 다른 글

백준 2775번 (C++)  (0) 2020.08.27
백준 10250번 (C++)  (0) 2020.08.25
백준 1193번 (C++)  (0) 2020.08.23
백준 2292번 (C++)  (0) 2020.08.23
백준 2839번 (C++)  (0) 2020.08.23