백준 2869번 <달팽이는 올라가고 싶다> - C++

나도 이 문에 빠르게 등반하고 싶었다.. 근데 생각보다 시간을 잡아먹었다.

얘 역시 ezpz한데? 하고 도전을 했는데.. 음 예상 외로 복잡하게 생각했달까

 

처음 무지성으로 작성했던 코드를 보자

#include <algorithm>
#include <cmath> //C++
#include <iostream>
#include <math.h> //C
#include <string>
#include <vector>

using namespace std;

int main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

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

  int day = 1;
  int height = v-a;
  int mok = height/(a-b);
  if(mok == 0 ) mok = 1;
  day += mok;
  cout << day;
  return 0;
}

이거는 잇지.. 말이 안 된다

 

그저 몫만 계산했다. 몫이 0일 때는 하루로 계산하고. 고려 안 한 점(고려하지 않은 점을 고려한 것도 다 고려하지 못했다)

• a와 b가 같을 때 (즉 나누는 수 = 분모가 0을 때)
• 낮에 올라간 높이에서 정상에 도달할 때를 무조건 빼버린 것
  • 무슨말이냐면,  a:5, b:2 h:10을 3일동안 오르고 미끄러지고를 반복해서 9미터지점에 이르렀다. 이때 a인 5를 올라가면 정상에 도달한다. 이것을 정상에서 a 빼버린 상태로 계산했다.
    • 문제가 뭐냐면, 총 높이를 5미터로 계산해 버린다는 것이다. 이런 방식을 채택할 거였으면, '정상의 높이가 9미터였을 때'로 바꾸는 방법을 고안해야 했는데, 답을 알고 있지 않는 이상 이것은 불가능하다
• 몫이 0일 때는 대체 뭐 어쩌려고 적어둔 걸까..? 아마 분모가 분자보다 클 경우를 산정한 것 같다.

 

기록해둔 메모를 보자 (사실 나와의 대화에 가까움 좌뇌랑 우뇌랑 general한 질문에 sharp한 답변 싸움)

낮에 A미터 올라가고, 밤에 B미터 미끄러짐 만 하루동안 A-B미터 올라감 정상에 도달하면(낮에 A미터에 올라가는 것에 성공했으면) 미끄러지지 않음 정상에서 A미터를 제외한 거리를 높이로 설정을 하면 안 되구나 h를 a-b로 나눈 나머지가 a보다 작을 때! 날짜 = 몫 + 1 이 되어야 겠구나 -> a-b로 나눈 나머지는 무조건 a보다 작지 않냐..? h를 a-b로 나눈 몫을 m이라 하면, a-b를 m-1과 곱하자 -> 여기에 a를 더했을 때 h이상이면 day = m, 작으면 m+1 XXXXXXXXX 이게 (a-b)*n + a >= h 여야 하잖아 (a-b)*n >= h-a이면 되는 거 아녀? 2 1 5 보자 1 * n >= 3 day = (h-a)/(a-b) + 1 나누어 떨어지지 않는 경우는?? 무조건 몫+1 하면 되나 h 7    a 4  b 2 3/2 + 1

이렇게 나의 think.txt파일에 쓰여 있다.

 

총 세 가지 풀이 방식을 생각했다.

 

h를 a-b로 나눈 나머지를 통해 총 day에 +1을 할 지 말 지. 그런데 이것은 틀렸습니다. a-b로 나머지를 계산하면, 무조건 a보다 작다 ㅋㅋㅋㅋ (X)

 

h를 a-b로 나눈 몫을 계산하고, (a-b)*(몫-1) + a를 해서 h이상이면 m 작으면 m+1 이것도 논리적으로 말이 안 된다.

처음 몫을 계산했을 때 나누어 떨어지는 수라 이미 등반이 끝났을 수도 있다.(물론 마지막 미끄러짐이라는 오류를 포함)

(a-b)*(몫-1) + a가 h보다 작을 수가 없다. (사칙연산 다시 공부해야 할 듯)

 

그냥 숫자 그대로 표현해 보자.

(a-b)*n + a ≥ h면 되는 거 아니냐? 간단하잖냐. 맞다

이항해서 n만 남기자

n ≥ (h-a) / (a-b) 이다

 

그렇다면 총 일 수 day =  (h-a) / (a-b) + 1 이다. 왜 1을 더해주냐면, 저기 위에 +a부분은 낮에 올라간 높이를 나타내기 때문이다.

그리고 분모가 0인 경우 즉, a==b일 때는 계산이 불가능하기 때문에 무조건 하루(낮에 등반)만에 등반이 완료되는 높이가 주어질 것이다.

 

완성된 코드를 보쟈

#include <algorithm>
#include <cmath> //C++
#include <iostream>
#include <math.h> //C
#include <string>
#include <vector>

using namespace std;

int main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

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

  if(a == b){
    cout << 1;
    return 0;
  }
  int n = (v-a) / (a-b) + 1;
  if( (v-a) % (a-b) != 0 ) n++;

  cout << n;
  return 0;
}

 

 

하나 추가한 사항으로, 나누어 떨어지지 않는 경우는 하루가 더 필요하므로!! n(위에서 언급한 day)에 1을 더해준다.

 

끄읏~