[Baekjoon] 2869번 달팽이는 올라가고 싶다 (C++, Python)

[Baekjoon] 2869번 달팽이는 올라가고 싶다 (C++, Python)

 

목차

 

 

 

https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

 

원래 그냥 돌린다면 이렇게 돌릴 것이다. 그러나 시간 제한이 있고 이것보다 빠르게 처리할 수 있는 방법이 있다.

#include <iostream>
using namespace std;
int main() {      
    int a,b,v, i, s=0;
    cin >> a >> b >> v;    
    
    for (i=0; s<v; i++){
    	s += a;
    	if (s >=v) {
    		break;	
		}
		s -= b;
	}
	cout << i+1;
    
}

 

C++

 

방법 1 - 2020KB, 0ms, 218B

 

v%(a-b)로 처리하지 않은 이유 : v에 대하여 (a-b)만큼씩만 움직이는 것을 가정한 것이 틀리기 때문

달팽이는 a만큼 올라갔다가 b만큼 내려온다.

즉, 그 날의 최고치는 +a까지 올라간 후 +a-b가 되는 것.

 

그렇기 때문에 (v-a)에 대한 나머지를 기반으로 날짜를 계산한다.

 

만일 (v-a)가 (a-b) step으로 나눴을 때 나머지가 0이면, 일수+1이 최종 날짜. 이 때 1은 a만큼 올라오는 다음 날을 의미

 

만일 (v-a)가 (a-b) step으로 나눴을 때 나머지가 0보다 크면, 일수+2이 최종 날짜. 이 때 2 중 1은 나머지가 존재한만큼 하루 더 올라가야하기 때문이며 나머지 2 중 1은 a만큼 올라오는 다음 날을 의미.

 

 

 

#include <iostream>
using namespace std;
int main() {      
    int a,b,v;
    cin >> a >> b >> v;     
    if ((v-a)%(a-b)==0) cout << int((v-a)/(a-b)) + 1; 
    else if ((v-a)%(a-b)>0) cout << int((v-a)/(a-b)) + 2;
}

 

방법 2 - 1112KB, 0ms, 120B

 

하루 a-b만큼 올라감. 이와 관련하여 방법 1처럼 a만큼 뺀 상태까지 올라간 날짜 +1을 진행해도 좋으나 마지막 날까지의 (a-b) 계산을 위해 V미터의 나무를 올라가는 날 V-b만큼 올라간다고 판단가능.

조금 더 정리해서 이야기하면 마지막 날 a만큼 올라가는 것을 끝으로 계산이 진행되는 것이 일반적이나 a만큼 마지막 날 올라가고 b만큼 떨어지는 것을 고려하여 V-b를 사용.

 

#include<stdio.h>
int main() {      
    int a,b,v;
    scanf("%d%d%d",&a,&b,&v);   
    printf("%d",(v-b-1)/(a-b)+1);
}

 

Python

 

방법 1 - 29200KB, 68ms, 61B

 

a,b,v = map(int, input().split())
print(int((v-b-1)/(a-b)+1))

 

방법 2- 29200KB, 72ms, 74B

 

a,b,v = map(int, input().split())
print((v-a)//(a-b)+1+(((v-a)%(a-b))!=0))