https://www.acmicpc.net/problem/9367
오랜만에 글을 쓰네요. 정말 어이가 없게 푼 문제가 있는데, 이게 풀이법이 널린 문제가 아니라서 이렇게 공유하고자 글을 작성합니다.
25%에서 계속 틀리길래
Gemini Pro 2.5와 머리를 맞대고 대체 논리적으로 틀린 부분이 없는데 왜 틀렸을까... 찾아봤는데
수리비 계산하는 부분에서 문제가 있었습니다.
double damageCost = (double) (car.price * severity) / 100;
double damageCost = car.price * (severity / 100.0);위 두 코드의 차이인데요, 위에가 정답이고 아래가 틀린 답이었습니다.
왜냐하면 문제 설명이 영어에서 한국어로 번역되면서 누락된 부분이 있었습니다.
백분율 단위로 해야하기 때문에 100.0을 사용하면 안 됐습니다.
하지만 저 두 코드의 연산 값의 차이는 어떻게 생기게 될까요? 그 이유는 아래에서 설명하겠습니다.
풀이 방법
- 자동차 정보에 대한 class를 만들고 Map <"차 이름", 자동차 정보 class> 형태로 저장
- 첩보원의 렌탈 상태를 저장하는 class를 만들고, TreeMap<"첩보원 이름", 렌탈 상태 class> 형태로 저장 (이름을 사전순으로 정렬하기 위함)
- 'p'의 경우, 이미 렌탈 중인 경우 비일관성
- 'r'의 경우, 빌린 차가 없는데 반납하면 비일관성
- 'a'의 경우, 빌린 차가 없는데 사고내면 비일관성
- 위 경우를 다 따졌는데 아직 렌탈중인 경우 비일관성
- 결과 출력
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
// 자동차 정보를 저장하는 클래스
static class Car {
int price, initialFee, kmFee;
Car(int p, int q, int k) {
this.price = p;
this.initialFee = q;
this.kmFee = k;
}
}
// 첩보원의 현재 렌탈 상태를 저장하는 클래스
static class SpyState {
boolean isRenting = false;
String carName;
int totalCost = 0;
boolean inconsistent = false;
void rent(String carName, int initialFee) {
this.isRenting = true;
this.carName = carName;
this.totalCost += initialFee;
}
void processReturn(int distance, int kmFee) {
this.isRenting = false;
this.carName = null;
this.totalCost += distance * kmFee;
}
void processAccident(double damageCost) {
// 수리비는 올림 처리
this.totalCost += Math.ceil(damageCost);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testCases = Integer.parseInt(br.readLine().trim()); // 테스트 케이스 수 읽기
StringBuilder finalOutput = new StringBuilder();
for (int t = 0; t < testCases; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); // 자동차 종류 수
int m = Integer.parseInt(st.nextToken()); // 사건 로그 수
Map<String, Car> carInfos = new HashMap<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String carName = st.nextToken();
int p = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
carInfos.put(carName, new Car(p, q, k));
}
// 첩보원 이름(String)을 키로, 첩보원의 상태(SpyState)를 값으로 저장
Map<String, SpyState> spies = new TreeMap<>();
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
st.nextToken(); // 시간 정보는 이 문제의 논리에서는 사용되지 않음
String spyName = st.nextToken();
char eventType = st.nextToken().charAt(0);
// 첩보원 정보가 없으면 새로 생성
spies.putIfAbsent(spyName, new SpyState());
SpyState currentSpy = spies.get(spyName);
// 이미 비일관성으로 판명된 첩보원은 더 이상 처리하지 않음
if (currentSpy.inconsistent) {
continue;
}
switch (eventType) {
case 'p': // Pick-up
String carName = st.nextToken();
// 이미 다른 차를 빌리고 있다면 비일관성
if (currentSpy.isRenting) {
currentSpy.inconsistent = true;
} else {
Car car = carInfos.get(carName);
currentSpy.rent(carName, car.initialFee);
}
break;
case 'r': // Return
int distance = Integer.parseInt(st.nextToken());
// 빌린 차가 없는데 반납하면 비일관성
if (!currentSpy.isRenting) {
currentSpy.inconsistent = true;
} else {
Car car = carInfos.get(currentSpy.carName);
currentSpy.processReturn(distance, car.kmFee);
}
break;
case 'a': // Accident
int severity = Integer.parseInt(st.nextToken());
// 빌린 차가 없는데 사고를 내면 비일관성
if (!currentSpy.isRenting) {
currentSpy.inconsistent = true;
} else {
Car car = carInfos.get(currentSpy.carName);
// 수리비 = 원가 * (파손율 / 100)
double damageCost = (double) (car.price * severity) / 100;
currentSpy.processAccident(damageCost);
}
break;
}
}
// 모든 이벤트를 처리한 후, 여전히 차를 빌리고 있는 첩보원은 비일관성
for (SpyState spy : spies.values()) {
if (spy.isRenting) {
spy.inconsistent = true;
}
}
// 결과 출력
for (Map.Entry<String, SpyState> entry : spies.entrySet()) {
String spyName = entry.getKey();
SpyState spyState = entry.getValue();
finalOutput.append(spyName).append(" ");
if (spyState.inconsistent) {
finalOutput.append("INCONSISTENT\n");
} else {
finalOutput.append(spyState.totalCost).append("\n");
}
}
}
System.out.print(finalOutput);
}
}Java의 정수 연산과 부동 소수점 연산의 차이
정수(int)는 이진수로 직접 표현되며, 연산은 해당 범위 내에서 항상 정확하게 수행됩니다.
반면, 부동 소수점 숫자(double)는 IEEE 754 표준을 따릅니다. 이 표준에 따르면, 부동 소수점 숫자는 부호 비트, 지수, 가수(mantissa)의 세 부분으로 구성됩니다.
double 타입은 1비트의 부호, 11비트의 지수, 52비트의 가수를 사용하여 64비트로 표현됩니다.
이진 시스템에서 숫자를 저장하는 방식 때문에 모든 십진수 값을 정확하게 표현할 수 없으며, 이로 인해 작은 정밀도 오차가 발생할 수 있습니다.
십진수 소수를 이진수로 변환하는 기본 원리는 다음과 같습니다.
- 소수 부분에 2를 곱합니다.
- 곱셈 결과의 정수 부분(0 또는 1)을 기록합니다. 이 정수 부분이 이진수 소수점 아래 자리가 됩니다.
- 결과에서 정수 부분을 제외한 소수 부분에 다시 2를 곱합니다.
- 이 과정을 소수 부분이 0이 되거나, 필요한 정밀도에 도달할 때까지 반복합니다.
- 기록한 정수 부분들을 순서대로 나열하면 이진수 소수가 됩니다.
십진수 0.625를 이진수로 변환하는 과정을 단계별로 살펴보겠습니다.
단계 1: 0.625에 2를 곱하기
0.625 x 2 = 1.25
- 정수 부분: 1 (첫 번째 이진수 소수점 자리)
- 남은 소수 부분: 0.25
단계 2: 남은 0.25에 2를 곱하기
0.25 x 2 = 0.5
- 정수 부분: 0 (두 번째 이진수 소수점 자리)
- 남은 소수 부분: 0.5
단계 3: 남은 0.5에 2를 곱하기
0.5 x 2 = 1.0
- 정수 부분: 1 (세 번째 이진수 소수점 자리)
- 남은 소수 부분: 0.0
남은 소수 부분이 0이 되었으므로 변환 과정이 끝납니다.
기록된 정수 부분들을 위에서 아래 순서로 나열하면 1, 0, 1이 됩니다.
0.101(2)로 표현할 수 있겠습니다.
십진수 0.1은 이진수로 정확하게 표현할 수 없는 무한소수가 됩니다. 이 과정을 살펴보겠습니다.
단계 1: 0.1에 2를 곱하기
0.1 x 2 = 0.2
- 정수 부분: 0
- 남은 소수 부분: 0.2
단계 2: 남은 0.2에 2를 곱하기
0.2 x 2 = 0.4
- 정수 부분: 0
- 남은 소수 부분: 0.4
단계 3: 남은 0.4에 2를 곱하기
0.4 x 2 = 0.8
- 정수 부분: 0
- 남은 소수 부분: 0.8
단계 4: 남은 0.8에 2를 곱하기
0.8 x 2 = 1.6
- 정수 부분: 1
- 남은 소수 부분: 0.6
단계 5: 남은 0.6에 2를 곱하기
0.6 x 2 = 1.2
- 정수 부분: 1
- 남은 소수 부분: 0.2
단계 6: 남은 0.2에 2를 곱하기
0.2 x 2 = 0.4
- 정수 부분: 0
- 남은 소수 부분: 0.4
이 단계부터 0.2로 돌아와 2단계부터의 과정이 반복되는 것을 알 수 있습니다. 이처럼 소수 부분이 0이 되지 않고 계속해서 순환되므로, 십진수 0.1은 이진수로 무한소수가 됩니다.
기록된 정수 부분들을 순서대로 나열하면 0.0001100110011...(2)가 됩니다.
컴퓨터는 이 무한히 반복되는 소수를 유한한 비트 수(예: double의 경우 52비트의 가수)에 맞게 잘라내서 저장합니다. 이 과정에서 발생하는 아주 미세한 차이가 정밀도 오차의 원인이 됩니다.
public static void main(String[] args) throws Exception {
double sum = 0.0;
for (int i = 0; i < 10; i++) {
sum += 0.1;
}
System.out.println("0.1을 10번 더한 결과: " + sum); // 출력: 0.9999999999999999
}이 코드의 결과는 IEEE 754 표준을 따르는 double 타입의 한계를 보여줍니다. 위에서 언급했듯이, 십진수 0.1은 이진수로 정확히 표현될 수 없는 무한소수입니다.
Java의 JVM은 IEEE 754 표준의 반올림 규칙(가장 가까운 값으로 반올림)을 따르지만, 이는 근본적인 정밀도 문제를 해결하지는 못합니다. 0.1의 근사값을 10번 더하면, 각 연산 단계에서 미세한 오차가 누적되어 최종적으로 1.0이 아닌 0.9999999999999999라는, 육안으로는 구분하기 어려운 오차가 발생합니다.
이는 Java(및 일반적으로 컴퓨팅)의 설계로, 개발자는 애플리케이션의 요구 사항에 따라 필요한 정밀도를 고려하여 데이터 타입을 신중하게 선택해야 합니다.
다시 문제 상황으로 돌아가서,
double damageCost = (double) (car.price * severity) / 100;
double damageCost = car.price * (severity / 100.0);두 표현식의 근본적인 차이는 나눗셈 연산이 부동 소수점 연산이 되는 시점에 있습니다.
- 표현식 1: (double) (car.price * severity) / 100;
- 나눗셈 / 100은 int / int로 수행되어 소수 부분이 잘립니다.
- 이후 (double) 캐스트는 이미 잘린 정수 결과에 적용됩니다.
- 표현식 2: car.price * (severity / 100.0);
- 나눗셈 / 100.0은 int / double (자동으로 double / double로 승격)로 수행되어 소수 부분이 처음부터 보존됩니다.
따라서 damageCost 값이 계속 연산이 될수록 소수 부분의 유무로 인해 값이 오차가 생기게 된 것이죠.
이후 문제 조건인 만일 소수점 이하의 어떤 비용이 발생한다면 그 비용은 청구서에 올라가기 전 올림하여 합산된다. 를 위해 소수 첫째 자리 올림 Math.ceil() 함수를 수행할 때, 값이 달라지게 된 것 이었습니다.
'Development > PS' 카테고리의 다른 글
| [PS] 백준 오아시스 재결합 Java 풀이 (+모노톤 스택에 관하여) (1) | 2024.11.28 |
|---|---|
| [PS] 백준 도전 숫자왕 java 풀이 (비트마스킹으로 모든 경우의 수 찾기) (0) | 2024.11.26 |
| [PS] 코드트리 나무 타이쿤 java 풀이 (0) | 2024.11.25 |
| [PS][PCCP 기출문제] 3번 / 충돌위험 찾기 java 풀이 (+조건문 없음, 64 lines) (1) | 2024.11.02 |
| [PS] 백준 1107 리모컨 java 풀이 (0) | 2024.10.31 |