2020. 1. 10. 07:54ㆍAlgorithm/문제풀이
https://www.acmicpc.net/problem/2869
2869번: 달팽이는 올라가고 싶다
문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽
www.acmicpc.net
이 문제는 특정 숫자에 대해 n번 일때 최대 높이를 구하는 것이 중요하다. V미터 까지 A만큼 올라갔다가 도달하지 못하면 일정 숫자만큼 미끄러질 때 몇일 만에 V만큼 도달하는지 푸는 문제이다.
"처음에는 단순하게 반복문만 돌리면 편하게 풀 수 있겠는걸"?라는 단순한 생각으로 접근했다.
그런데 시간 제한이 1초도 아닌 0.15초인 것이다.
바로 반복문은 안되겠구나 싶어서 다른 방법을 찾게되었는데 하루마다 최대 높이가 등차수열 특징을 갖고 있는 것을 발견하여 아래의 공식을 사용하여 문제를 해결했다.
백준 페이지에 있는 예제를 통해 식 유도를 하겠다. 하루 마다 최대 높이를 적어보면 일정한 등차를 알 수 있다. V만큼 도달하기 위해 몇일 만큼 걸리는지 구하기위해 n을 제외하고 왼쪽으로 모두 옮긴 식을 코드로 구현하면 됩니다.
주의 해야할 점은 분수의 값이 2.xx, 1.xxx 같이 나올 수 있다는 것이다. 2.xxx일은 결국 3일이 필요하다는 말이다. 따라서 math.h 함수를 통해 올림해주어야한다.
코드
#include <stdio.h>
#include <math.h>
int main(){
int A, B, V;
scanf("%d %d %d", &A, &B, &V);
printf("%d", (int)(ceil((double)(V-A)/(double)(A-B)+1)));
}
응용해서 풀어볼만 한 문제
1712번 손익분기점
https://www.acmicpc.net/problem/1712
1712번: 손익분기점
월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로
www.acmicpc.net
'Algorithm > 문제풀이' 카테고리의 다른 글
| 부르트포스 - 백준 체스판 다시 칠하기 1018 (0) | 2020.01.21 |
|---|---|
| 부르트포스 - 백준 블랙잭 2798 (0) | 2020.01.21 |
| 백준 11729 하노이 탑 이동 순서 (0) | 2020.01.10 |
| 백준 1002 터렛 (0) | 2020.01.10 |
| 백준 1712 손익분기점 (0) | 2020.01.10 |