백준 알고리즘 2869번: 달팽이는 올라가고 싶다 C언어

문제 출처: https://www.acmicpc.net/problem/2869

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

1. 코드

#include <stdio.h>
#include <math.h>

int main(void)
{
    int a, b, v;
    double result;
    
    scanf("%d %d %d", &a, &b, &v);
    
    result = ceil((double)(v - b) / (a - b));
    printf("%.0f", result);
    
    return 0;
}

 

2. 문제 해결 방식

먼저 예제에 등장하는 2 1 5로 먼저 풀어보자.

	1m	2m	3m	4m	5m
1일 - 낮	↗	↗
1일 - 밤		↘
2일 - 낮		↗	↗
2일 - 밤			↘
3일 - 낮			↗	↗
3일 - 밤				↘
4일 - 낮				↗	↗

그렇다면 낮을 x라고 가정할 때 표에서 x는 4이고, 밤은 3이기에 x - 1로 가정한다. 그러면 하나의 조건 부등식을 만들 수 있는데 ax - b(x - 1) ≥ v라는 식이 완성이 되는데 ax는 달팽이가 오르는 수식이고 b(x - 1)은 달팽이가 내려가는 수식이다. 그리고 문제를 해결하려면 ax-b(x-1)이 v와 같거나 크면 그때의 x의 값이 문제에 답이라고 볼 수 있다.

그렇다면 이 식을 x만 따로 정리해보도록 하자.

ax - b(x - 1) ≥ v

ax - bx + b ≥ v

x(a - b) + b ≥ v

x(a - b) ≥ v - b

x ≥ (v - b) / (a - b)

최종적으로 나온 식은 x ≥ (v - b) / (a - b)이지만 이것을 적용하면 답은 안 나올 것이다. 아직 예외적인 게 있기 때문이다.

예외적인 상황에서 하나를 예로 3 1 6이 있다.

	1m	2m	3m	4m	5m	6m	7m
1일 낮	↗	↗	↗
1일 밤			↘
2일 낮			↗	↗	↗
2일 밤					↘
3일 낮					↗	↗	↗

x ≥ (v - b) / (a - b)이 식으로 계산한다면 x ≥ 2.5가 나올 것이다. 그 이유는 이 표를 보면 3일 낮에는 최종적으로 7m를 도달하는데 v는 6이므로 3이 나와야 하지만 0.5가 적게 나온 것이다.

그렇다면 만든 식에서 계산을 통해 아주 조그마한 소수라도 나온다면 그것은 이미 도달했지만 v가 더 작기 때문에 그렇게 나온 것이기 때문에 헤더 파일 math.h의 함수인 ceil을 이용하여 올림을 하여 2.5를 3으로 올려주면 문제는 해결된다.

 

3. 느낀 점

이 문제 또한 나에게 어려웠다. 결국 이번에도 검색을 해보았지만 이 공식을 유도하는 방법이 어째서 이렇게 유도되는지 나와있지 않고 그냥 공식만 알려주거나 올림을 하는 이유도 그냥 올림을 하라고 나와있어서 정말 많이 어려웠다.

검색을 하다가 이런 식으로 유도되는 이유를 알 수 없어서 이것을 풀어본 친구에게 부탁을 하여 알게 되어 이렇게 정리한다. 나중에 시간이 날 때 천천히 여러 번 풀어보아야 할 것 같다.