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

달팽이는 올라가고 싶다 성공출처다국어분류

Bronze II

수학

난이도 제공: solved.ac — 난이도 투표하러 가기

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.15 초 (추가 시간 없음)	128 MB	65103	15574	13196	26.012%

문제

---

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

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

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

입력

---

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

---

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

예제 입력 1

---

2 1 5

예제 출력 1

---

4

출처

---

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #2 1번

문제를 번역한 사람: baekjoon

데이터를 추가한 사람: CHULMING jm0707

문제의 오타를 찾은 사람: hellogaon

빠진 조건을 찾은 사람: jh05013

알고리즘 분류

---

수학

시간 제한 안내

---

아래 적혀있지 않은 시간 제한은 언어 도움말에 적혀있는 기준을 따른다.

C# 6.0: 0.25초

node.js: 0.25초

C# 3.0: 0.25초

VB.NET 2.0: 0.25초

VB.NET 4.0: 0.25초

​

---

아직까지는 문제 푸는데 몇 분 걸리지 않는 난이도이다.

​

이번에도 문제 자체는 어려운 부분이 없어서 그냥 슥슥 작성해서 제출했는데 시간초과가 되어버렸다.

​

봐 보니 브론즈2 난이도임에도 정답비율이 26%밖에 되지 않는것은 이와 같은 이유인듯 하다.

​

학습능력이 부족한 편...

​

5달 전과 똑같은 짓을 하고 있다 ㅋㅋㅋㅋㅋ

​

​

어쨌든 문제 자체는 크게 어렵지 않다.

밤에 미끄러지기 전에 낮에 도착하면 끝난다는 것만 생각해서 작성해주면 되는 문제

​

​

5개월 전 코드

 

#include <iostream>
#include <cmath>
using namespace std;

int main(){
	double a, b, v;
	cin >> a >> b >> v;
	int d = 1;
	v -= a;
	if ( v > 0)
		d  += int(ceil(v/(a-b)));
	cout << d;
}

보아하니, 기본 소요시간 1일로 잡고...

전체 높이 V에서 낮에 올라가는 높이 A를 우선 뺐다. 왜냐하면 밤이 되기전 낮에 다 올라갈 수 있는 경우를 미리 상정해야 하기 때문에.

미리 A를 안 빼주고 (낮에 올라가는 높이 - 밤에 올라가는 높이) 로 나눠주면 잘못된 답이 나와버린다.

​

아무튼, V에서 A를 뺀 후 V가 0보다 크면...

그러니까 낮에 올라가고도 올라가야 하는 높이가 남아있다면

​

나머지 높이를 (A-B)로 나눠준 값을 올림한 값을 소요일에 추가해준다.

​

​

이번에 작성한 코드

#include <iostream>
using namespace std;

int main(){
  int A, B, V;
  cin >> A >> B >> V;

  V -= A;

  if(V % (A - B) == 0) cout << V / (A - B) + 1;
  else cout << V/(A-B) + 2;

5개월 전 작성한 코드랑 기본적으로 생각하는 건 똑같다.

​

전체높이 V에서 우선 A를 빼준 후 마찬가지로 (A-B)로 나눠주는 것.

다만 이번에는 ceil 함수를 사용하지 않고,

​

(A-B)로 나누어 준 값이 딱 떨어진다면 낮에 한 번 올라가면 정상에 도착한다는 뜻이므로 나눠준 몫에 + 1한 값이 소요일이며

​

(A-B)로 나누어 준 값이 나머지를 가진다면 낮->밤->낮 을 거쳐야 정상에 도착한다는 뜻이 되므로 나눠준 몫에 + 2 한 값이 소요일이 된다

​

라는 것을 이용해서 값을 도출했다.

​

​

이렇게 나누기를 활용해서 수식으로 바로 값을 도출하면 시간제한에 걸리지 않지만

처음 내가 작성한 코드의 경우에는 나누기를 사용하지 않고 반복문을 통해 계속 같은 값을 빼주는 방법을 하였더니 시간제한에 걸렸다.

​

그래서 갑자기 든 생각

​

그렇다면 시간 차이가 얼마나 나는 거였을까

​

그래서 직접 해봤다.

​

2869.cpp (반복문 없는 코드)

#include <iostream>
#include <time.h>

using namespace std;

int main(){
  time_t start, end;
  int A, B, V;
  cin >> A >> B >> V;

  start = time(NULL);

  V -= A;

  if(V % (A - B) == 0) cout << V/(A-B) + 1;
  else cout << V/(A-B) + 2;

  end = time(NULL);
  cout << "\n 소요시간 : " << end - start << "\n";

}

​

2869_2.cpp (반복문 있는 코드)

#include <iostream>
#include <time.h>
using namespace std;

int main(){
  time_t start, end;
  int A, B, V;
  int day = 1;
  cin >> A >> B >> V;

  start = time(NULL);

  V -= A;

  for(;V > 0; V -= A){
    V += B;
    day += 1;
  }
  cout << day;

  end = time(NULL);

  cout << "\n 소요시간 : " << end - start << "\n";
}

}

수행 결과

시간이 소수점자리까지 표시가 되지 않아 모르겠지만 직접 실행했을 때 엔터와 동시에 값이 도출되었던 거 보면 수식으로만 실행했을때는 수행시간이 극히 짧았다.

​

하지만 반복문을 사용한 코드의 경우에는 평균 3~4초의 수행결과를 보여주었다.

​

입력값은 두 코드 모두 동일하게 worst case라고 판단되는

​

A : 1 B : 0 V : 1,000,000,000 으로 해 주었다.

​

​

앞으로 할 때는 조금 더 신경써서 풀어야 겠다는 교훈을 주는 문제였다.

​