문제 출처: https://www.acmicpc.net/problem/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. 느낀 점
이 문제 또한 나에게 어려웠다. 결국 이번에도 검색을 해보았지만 이 공식을 유도하는 방법이 어째서 이렇게 유도되는지 나와있지 않고 그냥 공식만 알려주거나 올림을 하는 이유도 그냥 올림을 하라고 나와있어서 정말 많이 어려웠다.
검색을 하다가 이런 식으로 유도되는 이유를 알 수 없어서 이것을 풀어본 친구에게 부탁을 하여 알게 되어 이렇게 정리한다. 나중에 시간이 날 때 천천히 여러 번 풀어보아야 할 것 같다.
'컴퓨터 > 백준 알고리즘' 카테고리의 다른 글
백준 알고리즘 2775번: 부녀회장이 될테야 C언어 (4) | 2020.02.08 |
---|---|
백준 알고리즘 10250번: ACM 호텔 C언어 (2) | 2020.02.07 |
백준 알고리즘 4673번: 셀프 넘버 C언어 (개선) (0) | 2020.02.05 |
백준 알고리즘 1193번: 분수찾기 C언어 (8) | 2020.01.31 |
백준 알고리즘 2292번: 벌집 C언어 (2) | 2020.01.29 |