본문 바로가기
BOJ

[C] 백준 2869번: 달팽이는 올라가고 싶다

by 야호호코코 2018. 7. 25.
반응형

 수학적 지식이 필요한 문제이다. 이분 탐색법으로도 풀 수 있지만 항상 더 짧고 간단하게 끝내는 것이 좋지 않은가? 그래서 한 줄 짜리 수식 하나로 끝냈다. 시간 제한을 보면 알 수 있듯이 상수시간, O(1) 내로 풀어야한다. 그래서 선택할 수 있는 방법이 한 줄 수식과 이분 탐색 밖에 없는 것이다. 아마 반복문을 쓰면 백퍼센트 시간 초과가 뜰 것이다.


 


 

입출력 예시


입력 

출력 

2 1 5 

4


입력 

출력 

10 3 54

8



정답 코드

#include <stdio.h>


int main() {

	int A, B, V;
	int day;

	scanf("%d %d %d", &A, &B, &V);

	day = (V - B - 1) / (A - B) + 1;

	printf("%d", day);


	return 0;

}


코드 설명


1. A, B, V를 입력받는다. 


2. 수식을 설명 하자면, 달팽이는 하루에 (A - B) 미터 씩 총 V미터를 올라가면 된다. 하지만 달팽이가 목표 지점에 도달한 날에는 미끄러지는 것을 감안하면 안되니 총 (V - B)미터를 올라가게 되는 것과 같다. 만약 (V - B)가 (A - B)로 딱 나눠 떨어지지 않으면 몫에 + 1 한 것이 정답이다 (하루 더 가니까). 근데 int형 이라서 나눠 떨어지는지 구분하기 귀찮으니까 (V -B)에 1을 미리 빼놓고 몫에 무조건 1을 더하는 것으로 처리한다.

반응형

'BOJ' 카테고리의 다른 글

[C] 백준 9012번: 괄호  (0) 2018.07.29
[C] 백준 2851번: 슈퍼 마리오  (0) 2018.07.25
[C] 백준 1769번: 3의 배수  (0) 2018.07.22