[백준] | C++ | 2869. 달팽이는 올라가고 싶다

개요

이제 실버2 입니다.

 

백준을 처음 풀때는 몰라도 친구에게 solved.ac 를 전수받고 난 뒤에는 '단계별로 풀어보기' 를 사용하기보단 그냥 나에게 맞다고 생각되는 티어의 분류에서 적당한 문제를 골라 풀었는데 이거 상당히 물건입니다,

 

뇌를 짜내야하는 실버 4 이상의 문제가 아닌 적당히 뇌를 쓸 수 있고 피로가 덜한 문제들을 풀 수 있었습니다. 이제 solved.ac 에서 하남자처럼 문제 안 골라도 됩니다.

그래서 오늘 풀 문제는 '일반 수학 1' 의 마지막 문제, 2869. 달팽이는 올라가고 싶다 입니다.

 

 

 

---

 

 

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

 

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

 

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

반복문으로 구현하면 쉬운편아닌가? 나와 역시 브론즈1 과는 수준이 맞지 않는군...

 

 

---

 

 

풀이

라고 생각했던게 제 불찰이였습니다.

아뿔싸. 카테고리가 '일반 수학 1' 이였죠.

어리석은 저는 그냥 무지성으로 반복문을 돌렸습니다.

 

총 길이 V가 주어지고 A와 B또한 주어지니 반복문으로 연산하면 구해지기야 하겠죠.

V가 늘어날수록 속도가 끔찍하게 느려지겠지만 말이죠...

 

#include<iostream>

using namespace std;

int main()
{
	int a, b, v;

	cin >> a >> b >> v;

	int p = 0;
	int d = 0;

	while (true)
	{
		d++;
		p += a;
		if (p >= v)
			break;
		p -= b;
	}
	cout << d;
}

 

반복문으로 구현한 코드입니다.

네... 당연하게도 시간 초과 입니다.

 

그냥 while(true) 돌면서 걸린 일 수(day)를 루프 한번마다 올려주고 달팽이의 현재 위치(position)에 a를 더했다가 b를 빼는걸 무한반복하면 끝입니다.

 

물론 이런걸 수학문제라고 낼 수 있는 곳은 초등학교정도겠죠.

 

접근 자체를 잘못했습니다.

간단하게 그림으로 봅시다.

 

나뭇가지의 길이가 V, 달팽이가 하루동안 가는 거리가 A, 자는동안 미끄러지는 거리가 B 니까 달팽이가 하루에 이동하는 거리는(A-B)미터 입니다.

 

그렇다면 V / (A-B) 를 할 경우 달팽이가 얼마나 지나야 올라가는 지 구할 수 있습니다.

물론 나머지가 1 이상이라면 하루가 더 지나야하겠죠.

하지만 문제에 적혀있던 조건은 하나가 더 있습니다.

 

또, 정상에 올라간 후에는 미끄러지지 않는다.

 

예외처리를 하나 해야합니다. 마지막에는 (A-B)미터가 아닌 A미터를 올라갑니다.

그러니 결국 달팽이는 총 (V-B)미터를 올라가는 것과 같습니다.

 

그렇기 때문에 (V-B) / (A-B)가 나누어 떨어지지 않으면 하루를 더 가야 하는것이죠.

 

다 풀었죠? 코드로 적어봅시다.

 

#include<iostream>

using namespace std;

int main()
{
	int a, b, v;

	cin >> a >> b >> v;


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

 

1트 성공!

 

아래 시간초과는 반복문 정공법입니다. 무시해주세요...

 

 

---

 

 

마치는 말

'일반 수학 1' 카테고리를 끝마쳤습니다. 어려워요.

그래도 조금 더 성장한 느낌이 듭니다.

쓸데없는 말 조금 하자면 마치는 말 쓰기 상당히 어렵습니다.
학교에서 이상한 교육한다음에 느낀 점 적으라고 하는 느낌이랄까요...

개요 같은 경우는 적으려고 하면 술술 적어내려가는 느낌인데 말이죠.