Algorithm/Problem

[BOJ]1206 사람의 수(S1, C++)

검은 까마귀 2024. 5. 2. 17:00

📋 개요

문제를 풀때 항상 2시간을 잡고 푸는데 2시간이 넘을때까지 풀지 못했다. 부동소수점의 문제인거같아 문자열로 형변환을 해서 풀이를 했지만, 어떤 이유인지 모르게 실패가 되었다...

 

질문게시판의 모든 반례도 넣어줬는데... 그래서 답안에 대한 복기를 해볼까한다.


🧩 문제

https://www.acmicpc.net/problem/1206

📝  형식 

📥 입력 📤 출력
첫째 줄에 N이 주어진다. 둘째 줄부터 N개의 줄에 각 문항의 평균 점수가 주어진다. N은 50보다 작거나 같은 자연수이고, 평균 점수는 0보다 크거나 같고, 10보다 작거나 같은 소수이다. 항상 소수점 셋째자리 까지 주어진다. 첫째 줄에 설문조사에 참여한 사람의 수를 출력한다. 만약, 가능한 정답이 여러가지라면, 가장 작은 값을 출력한다.

💡  예제

🔢 번호 📥 입력 📤 출력
1 3
0.500
0.250
0.125
8
2 1
0.000
1
3 2
0.500
0.300
10
4 2
0.500
0.301
106

 

🥲  내 코드 및 정답코드


📖  해설 및 느낀점

먼저 이문제를 이해하기 위해서는 "부동소수점의 오차"에 대해서 알아야한다.

double 타입의 부동소수점의 구조에 대해서 알아보자.

 

부호는 양수/음수를 결정하고 지수는 소숫점 자릿수를 결정, 가수는 실제 값을 의미한다.

 

그렇다면 "부동 소수점의 오류"에 대해서 보자.

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    double floatNum  = 4.039;
    
    floatNum = floatNum - (int)floatNum;
    floatNum = (floatNum * 1000.0) / 1000.0;
    
    cout << "4.039 X 1000 = " << (int)(floatNum * 1000)<< endl;
    //4.039 X 1000 = 38
    
    double floatNum2 = 4.039;
    
    floatNum2 = floatNum2 - floor(floatNum2);
    floatNum2 = round(floatNum2 * 1000.0) / 1000.0;
    
    cout << "4.039 X 1000 = " << (int)(floatNum2 * 1000)<< endl;
    //4.039 X 1000 = 39
    

    return 0;
}

 

난 4.039에서 소숫점자리수만 정수(int)로 바꾸기 위해서 해당 코드를 작성했다. 그런데 2가지의 경우가 다르게 결과가 나온다.

 

디버깅 해보면 아래와 같다.

 

난 분명 "4.039"를 넣었는데 0.03899999999가 나온다. 도대체 왜그럴까?

 

"부동"이라는 말에 focus를 맞춰보면 된다. double타입으로 입력을 받게되면 우리는 이에 근사한 값으로 근사치를 계산한다. 그 이유는 컴퓨터는 모든 것을 0과 1로 연산하기 때문이다. floatNum2는 이른 부동소수점에서 고정 소수점으로 바꿔서 처리를 하기때문에 소숫점 뒷자리만 원한다면 저렇게 연산을 할 수 있다는 것이다.

 

(나는 이 문제를 문자열로 바꿔서 처리하려고 했는데 어떤 로직에서 꼬인건지는 모르겠다....)

 

무튼 기본적으로 소수점을 제대로 추출해 낼 수 있으니 알고리즘을 짜야한다.

소숫점 셋째자리이기 때문에 1000명까지만 연산이 가능하다.

1명일때는 1/1

2명일때는 1/2, 2/2

3명일때는 1/3,2/3,3/3

4명일때는 1/4....

 

요로코롬 계산을 하여 계산한 소수점 셋째자리까지의 숫자중에 같은 값이 있는지 확인하면 된다.

물론 나눗값도 위의 과정을 거쳐 부동소수점 ➡️ 고정 소수점으로 처리해주는 연산과정이 필요하다.

 

이렇게 풀면되는데 S1인거 같은데 부동소수점의 오차에 대해서 모르면 삽질이 필요한거같다. 내가 삽질을 했다...

 

 

 

 

반응형

'Algorithm > Problem' 카테고리의 다른 글

[BOJ]1753 최단경로(G4, C++)  (0) 2024.05.14
[BOJ]14502 연구소(G4, C++)  (0) 2024.05.10
[BOJ]1189 컴백홈(S1, C++)  (0) 2024.04.30
[BOJ]1389 케빈 베이컨의 6단계 법칙(S1, C++)  (0) 2024.04.04
[BOJ]1269 대칭차집합(S4, C++)  (0) 2024.03.08