2869번 달팽이는 올라가고 싶다
https://www.acmicpc.net/problem/2869
이번 문제는 완전히 수학 문제였다.
먼저 문제에서는 달팽이가 막대를 타고 올라가는데 조건은 다음과 같다
- 막대의 높이는 V이다.
- 낮에 A 미터를 올라가고
- 밤에 B 미터를 미끄러진다
- 정상에서는 미끄러지지 않는다
최종적으로 달팽이가 막대를 올라가는데 며칠이 걸리는지 출력하면 된다.
반복문을 쓰면 간단하게 해결가능한 문제라고 생각하여 바로 작성해보았다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int v = sc.nextInt();
int count = 1;
int h = 0;
while(true){
h += a;
if(h >= v){
break;
}
h -= b;
if(h >= v){
break;
}
count++;
}
System.out.println(count);
}
}
간단하게 while문으로 반복하면서 값을 비교하고 count를 출력하는 코드이다.
하지만 시간제한 0.25초 라는 제한이 있어서 이대로 제출하면 시간초과가 난다.
문제를 어떻게 풀까 많이 고민했는데 이 반례를 보고 규칙을 찾을 수 있었다.
input : 12 10 102
output : 51
answer : 46
먼저 달팽이가 하루에 올라갈 수 있는 높이를 계산하였다.
(올라간 거리) - (내려간 거리) = (하루동안 올라갈 수 있는 높이)
A - B = H
그 다음 달팽이가 마지막날에 도달하는 높이를 구한다.
(막대 높이) - (내려간 거리) = (도달 높이)
V - B = mH
왜 마지막날에 도달하는 높이를 따로 구하냐면,
달팽이는 막대의 끝에 도달하면 더이상 미끌어지지 않는다는 조건이 있기 때문에
최대 높이에서 미끌어진 거리까지가 달팽이의 마지막 날이 될 수 있기 때문이다.
이제 이렇게 구해진 값들을 나누면 달팽이가 막대를 등반하기 위해여 걸리는 총 날짜가 나온다.
(도달 높이) / (하루동안 올라갈 수 있는 높이)
mH / H = result
하지만 여기서 문제가 하나 생긴다.
만약에 나눈 숫자가 정수가 아니라 소수점 자리로 나온다면?
예를 들어
5 1 6
이렇게 값이 주어지는 경우 이러한 결과가 나온다.
A - B = 5 - 1 = 4
V - B = 6 - 1 = 5
5 / 4 = 1.25
손으로 그려봐도 달팽이가 정상까지 가는데 2일이 걸리므로
소수자리가 나온다면 올림해주면 된다.
그래서 처음에 해당 결과값을 float 형식으로 받아와서 소수점을 올림처리 하는 코드를 작성하였다.
하지만 3번째 예제에서 답이 다르게 나왔는데 아래와 같이 입력이 주어졌을 경우
100 99 1000000000
아래와 같이 출력되었다.
999999872 // 출력된 값
999999901 // 정답
이유를 알수없어서 검색을 해보았는데 부동 소수점 연산의 정확도 문제라고 한다.
부동 소수점 연산의 정확도 문제는 컴퓨터 과학에서 자주 발생하는 문제입니다. 이를 이해하기 위해서는 부동 소수점 숫자가 어떻게 표현되는지 알아야 합니다.
부동 소수점 숫자는 컴퓨터에서 다음과 같은 형식으로 저장됩니다:
- 부호 비트: 숫자가 양수인지 음수인지를 나타냅니다.
- 지수: 숫자의 크기를 나타냅니다.
- 가수: 숫자의 정확한 값을 나타냅니다.
이러한 형식은 매우 큰 숫자나 매우 작은 숫자를 표현할 수 있게 해주지만, 정확한 값을 표현하는 데는 한계가 있습니다. 특히, 부동 소수점 숫자는 근사값으로 저장되기 때문에 정확한 값을 표현하지 못할 때가 있습니다. 이는 다음과 같은 이유로 발생합니다:
- 정밀도 제한: 부동 소수점 숫자는 제한된 비트 수로 표현되기 때문에, 매우 큰 숫자나 매우 작은 숫자를 표현할 때 정밀도가 떨어질 수 있습니다. 예를 들어, 999999901과 같은 큰 숫자를 부동 소수점 형식으로 변환하면 근사값으로 저장되기 때문에 999999872와 같은 값이 나올 수 있습니다.
- 반올림 오차: 부동 소수점 연산에서는 반올림 오차가 발생할 수 있습니다. 이는 소수점 이하의 값을 반올림할 때 발생하는 오차로, 특히 여러 번의 연산을 거치면서 누적될 수 있습니다.
- 표현 범위 제한: 부동 소수점 숫자는 표현할 수 있는 범위가 제한되어 있습니다. 이 범위를 벗어나는 숫자는 근사값으로 저장되기 때문에 정확한 값을 표현하지 못할 수 있습니다.
이러한 이유로 인해 부동 소수점 연산에서 오차가 발생할 수 있습니다. 이를 해결하기 위해서는 정수 연산을 사용하는 것이 좋습니다. 정수 연산은 정확한 값을 유지할 수 있기 때문에 부동 소수점 연산에서 발생하는 오차를 피할 수 있습니다.
이것을 해결하기 위해 if문을 사용하여 나머지가 0인 경우에는 그대로 출력하게 하고,
그 외에는 +1을 하도록 하게 코드를 수정하였다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt(); // 올라간 거리
int b = sc.nextInt(); // 내려간 거리
int v = sc.nextInt(); // 막대
if((v - b) % (a-b) == 0){
System.out.println((v - b) / (a-b));
} else{
System.out.println(((v - b) / (a-b))+1);
}
}
}
이걸로 문제를 해결할 수 있었다.