백준 2869번 달팽이는 올라가고 싶다(C언어)

문제 소개

난이도: 브론즈 1 

어렸을 때 수학 문제집에서 한번쯤은 다들 보셨을 문제 같다.

낮에는 a미터 올라가고 밤에는 b미터 내려가는 달팽이가 v미터의 막대기를 오르려면 며칠이 걸리는지 물어보는 문제이다.

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

입력

세 정수 a, b, v가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

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

예제 입력과 출력

입력1: 2 1 5
출력1: 4

입력2: 5 1 6
출력2: 2

입력3: 100 99 1000000000
출력3: 999999901

생각의 흐름

맨 처음에는 낮에 올라가는 높이와 밤에 내려가는 높이의 차를 구한 다음 그 값을 막대의 높이 이상이 될 때까지 몇 번 반복해 더해야 하는지 구하려 했다. 그래서 코드를 대충 이렇게 짰다.

#include <stdio.h>

int main() {
    int a, b, v;
    scanf("%d%d%d", &a, &b, &v);
    
    int h = 0, ans = 0;
    
    while(1) {
        ans++;
        h += a;
        if (h >= v) {
            break;
        }
        h -= b;
    }
    
    printf("%d", ans);
}

그런데 위 경우를 실행해봤더니만 엄청 오래 걸렸다.

그래서 다른 방법을 고민해 봤다.

어짜피 맨 마지막날에는 올라가기만 하지 않는가

원래 막대 길이에서 맨 마지막날에 올라가는 길이를 뺀 길이만큼 이동하는데 걸리는 날짜를 구해 1을 더하면 된다.

그래서 코드를 다음과 같이 짰다.

코드

#include <stdio.h>

int main() {
    int a, b, v;
    scanf("%d%d%d", &a, &b, &v);
    int d, i = a;
    
    while (1) {
        if ((v - i) % (a - b) == 0) {
            d = (v - i) / (a - b) + 1;
            break;
        }
        i--;
    }
    
    printf("%d", d);
}   

먼저 변수 a, b, v를 입력받은 후 i라는 변수를 선언해 낮에 올라가는 높이값을 저장한다.

마지막날 전날까지 올라간 거리를 달팽이가 올라가는데 며칠 걸리는지 구한다.
ㄴ> i 는 마지막날 낮에 올라간 거리를 뜻한다.
ㄴ> (v - i) 는 마지막날 전날까지 올라간 거리를 뜻한다.
ㄴ> (a - b) 는 하루에 올라가는 거리를 뜻한다.
ㄴ> i 의 값을 줄여가면서 (v - i)가 (a - b)로 나누어 떨어지는지 구한다.(하루에 달팽이는 (a - b)미터씩밖에 못 올라가므로 꼭 나누어 떨어져야 한다.)

마무리

설명이 주저리 주저리 길고 문장 하나하나가 읽기 어려울정도로 엉망인 것 같다. 필력을 더 키우고 와야 할 것 같다.