[백준 C++]2869번 문제 - 달팽이는 올라가고 싶다(설명 포함)

 

우선 시간제한 0.25초를 신경 쓰지 않고 생각없이 풀면.

#include<iostream>
#include<stdio.h>
#include<vector>
#include<string>
using namespace std;

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int a, b, v;
	cin >> a >> b >> v;

	int tmp = 0, count = 0;

	while (1)
	{
		tmp = tmp + a;
		count++;
		if (tmp >= v)
		{
			break;
		}
		else
		{
			tmp = tmp - b;
		}
	}

	cout << count;

	return 0;
}

 

이렇게 풀 수 있다.

 

1. tmp에 달팽이가 올라간 낮(a)을 더하고, count에 하루를 추가한다.

2. 만일 목표지점보다 같거나 높으면 중단한다

3. 부족하다면 밤으로 넘어가고 b만큼 뺀다.

 

단순히 이걸 while문을 통해 반복하다보면, 정답이 나오게 된다.

 

그리고 시간초과를 받을 것이다.

 

이 문제의 핵심은 단순한 문제를 생각의 흐름대로 코드를 진행시키는것이 아니라

알고리즘을 수학적으로 해석해서 간단하게 도출하는것이다.

 

우선 정답은,

#include<iostream>
using namespace std;

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int a, b, v;
    cin >> a >> b >> v;

    // 하루에 올라가는 순수 거리
    int day = (v - b - 1) / (a - b) + 1;

    cout << day;

    return 0;
}

 

단순하다.

이제 차근차근 int day = (v - b - 1) / (a - b) + 1 설명하겠다.

 

---

문제 상황

• a: 낮 동안 올라갈 거리
• b: 밤 동안 미끄러질 거리
• v: 꼭대기에 도달해야 할 거리

우리는 최소 며칠 만에 꼭대기에 도달할 수 있는지 계산해야 한다.

 

---

1. 하루 동안 이동하는 순수 거리

• 일반적인 하루에 이동하는 순수 거리는 낮에 올라간 거리에서 밤에 미끄러진 거리를 뺀 값이다:
                                                                 
                                                                 하루 순수 거리=a−b

---

2. 마지막 날에는 미끄러지지 않는다

• 마지막 날에는 꼭대기에 도달하면 더 이상 미끄러지지 않기 때문에
  마지막 날의 이동 거리 a는 충분히 계산된다.

 

• 즉, 마지막 날 이전까지는 하루 순수 거리 a−b를 사용해 목표에 접근해야 하고,
  마지막 날은 a만 추가하면 된다.

---

3. v−b가 의미하는 것

여기 까지 읽었으면 그럼 v-a가 맞는 표현 아닌가? 라는 생각을 할것이다.

day += (v-a) / (a-b);

 

원래는 이게 맞다.

 

하지만, 이렇게 진행하면 나누는 과정에서 나머지가 발생하게 되고, 이때 올림처리를 해야한다.

(예시들 넣어서 해보면 나머지가 생기는 경우가 존재한다)

 

그렇기 때문에 올림을 if를 활용해서 예외처리 하는것이 아니라.

 

---

4. 최소 일수 계산하기

핵심 아이디어:

1. 정수 나누기에서 소수점 올림 처리: 나눗셈 결과가 딱 나누어떨어지지 않으면 하루를 더 필요로 하므로 올림 처리가 필요하다.

올림 공식

이 공식을 (v-a) / (a-b) 에 적용하는것이다.

그럼 결과가 (v - b - 1) / (a - b) + 1; 나오게 된다.

 

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

 

이렇게 예외처리 할 필요없이

// 하루에 올라가는 순수 거리
int day = (v - b - 1) / (a - b) + 1;

 

이렇게 한줄로 끝나게 되는것이다.