https://www.acmicpc.net/problem/2869
문제
땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.
시간제한 > 0.25 초 (추가 시간 없음)
접근 방법 / 풀이 과정
처음 이 문제를 봤을 때. 어? 너무 쉬운 문제 아닌가?라고 생각했다.
그도 그럴게 A를 더하고 B를 빼고 과정을 거친게 V에 도달하면 끝나는 문제이기 때문이다.
int sum = 0;
int day = 0;
main : while(true) {
day++;
// sum에 A를 더한다
sum += A;
//sum이 V이상이면 종료
if( sum >= V)
break main;
sum -= B;
}
System.out.println(day);매우 간단한 코드이다.
하지만 당연하게도, 그리 간단한건 아닌 모양이다.
빨간 글씨가 나타났다.
문제에 조건이 걸려있었다. 시간제한 0.25초.
V의 범위는 10억
반복문을 사용할 수 없는 조건이다. 여기서 직감이 왔다. 이전 문제와 같이 규칙을 찾아서 해결하는 문제인 것이다.
1~2시간의 분석 끝에 규칙을 발견하였다!
A와 V를 각각 B로 뺄셈을 해준 후 V를 A로 나눈다. 이때 나머지가 없으면 몫은 나무를 오르는 데 걸린 일수와 같다. 나머지가 있으면 몫에서 +1을 해주면 된다.
import java.io.*;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine() , " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
int day = 0;
A -= B;
V -= B;
if( V % A != 0)
day = (V / A) +1;
else
day = V / A;
System.out.println(day);
}
}
느낀점
수학 (규칙)에 관련한 문제에서는 어김없이 나의 지능에 대한 의심이 들 때가 많다. 본 문제에 나온 규칙도, 아마 수를 잘 알고 있는 사람이라면 결과에 대한 원인을 바로 파악 할 수 있을 것이다.
그래도 하다보면 될 것이라고 생각하며 나의 두뇌가 발전하기를 바란다.
.
.
.
.
어느새 백준 단계별 문제풀기에서 8단계까지 완료하였다.
단계별 문제풀기에서는 알고리즘에 사용되는 다양한 기술과 수학적 정보를 알 수 있는데, 로직 공부에 매우 도움이 되고 있다.
하나하나 누적되는 완료박스가 너무나 뿌듯하다 :)
