[BaekJoon/백준] 2869번

이 문제 정말 애좀 많이 먹었다. 정말 컴퓨터를 뚫어지게 쳐다보면서 컴퓨터의 잘못을 의심하기까지 했다. 뭐 결과적으로 보면 컴퓨터의 잘못이기도 하지만 컴퓨터를 이해하지 못하고 있는 나의 잘못이기도 했다. 무슨말인지는 곧 알게 될 것이다.

 

달팽이가 V 라는 길이의 나무를 오르는데, 아침에는 A 만큼 올라가고 저녁에는 자는동안 B 까지 떨어진다. 다만 정상까지 오르고 나서는 떨어지지 않는다. 이 때 달팽이가 나무를 다 오르기까지 며칠이 걸리는지를 구하라는 문제다. 그냥 별 생각없이 처음 코딩을 했을 땐

 

(정답 X)

import java.util.Scanner;

public class Main {
    public static void main(String args[])
    {
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int B = scanner.nextInt();
        int V = scanner.nextInt();

        int day = 1;

        while(true) {
            V -= A;
            if(V<=0)
                break;
            else
                V +=B;
            day++;
        }
        System.out.println(day);
    }
}

시간초과라고 떴다. 그래서 시간제한을 보니 0.25초라고 나와있다. 이렇게 포문을 돌려가며 실행하는 구조는 아닌 것 같다.

그래서 나눗셈 연산을 해야겠다 라고 생각해서 A B V를 실수형 변수로 선언한 뒤에 나눗셈 연산을 해줬다.

 

(정답 X)

// 2 1 5의 경우
// 1일 2 1
// 2일 3 2
// 3일 4 3
// 4일 5 4

// A+(A-B)N >= V
// (A-B)N >= V-A
// N >= (V-A)(A-B)

import java.util.Scanner;

public class Main {
    public static void main(String args[])
    {
        Scanner scanner = new Scanner(System.in);
        float A = scanner.nextInt();
        float B = scanner.nextInt();
        float V = scanner.nextInt();

        int day;
        //Math.ceil은 올림 연산
        day = (int)Math.ceil((V-A)/(A-B))+1;

        System.out.println(day);
    }
}

그래도 답이 틀렸다고 한다. 여기서 도대체 뭐가 틀린건지를 모르겠어서 정말 돌아버리는 줄 알았다. 근데 float나 double 같은 실수형 변수의 특징에 대해 알고 있는가??? 내가 예전에 프로젝트를 진행하면서 float의 부정확성 때문에 연산 과정에서 애를 먹은 적이 있다. 무슨 말이냐면 float나 double 같은 실수형 변수들은 '부동소수점 방식' 으로 값을 저장한다.

 

대표적인 쉬운 예를 들어, 소수의 경우 무한소수도 있고 순환소수도 있는데 그런 값들은 데이터 저장에 있어서 어떠한 값으로 정확히 표현할 수가 없다. 또한 모든 실수를 8byte 혹은 12~16byte의 실수형 변수에 모두 담을 수도 없다. 실수는 무한히 많은데 이를 유한한 비트(실수형에 주어진 비트)로 표현할 수가 없다는 것이다. 이런 다양한 이유들로 컴퓨터는 그 값과 가장 근사한 값을 반환하도록 한다. 이것이 실수형 변수의 데이터 저장 특징이다. 실수형 변수가 이러한 방식으로 데이터 저장을 하기 때문에, 입력한 값이 무엇이던 직접 입력한 데이터와 실제 저장된 데이터에는 오차가 생기게 된다. 입력한 데이터의 가장 근사한 값으로 값이 저장되기 때문이다. 이를 테면 개발자가 실수형 변수에 1.0을 저장하더라도 그것이 0.999999999999999로 저장될 수도 있기 때문에 함부로 정수형으로 캐스팅하면 안된다. 개발자 입장에서는 1.0을 넣고 int형으로 캐스팅하면 1이 나올거라고 생각하지만 (int)0.999999999999999가 되어 0이 나올 수 있다는 점을 감안해야 한다. 

 

다시말해

수학적으로 실수는 무한히 많은데 이 실수를 유한 개의 비트로 표현하기 위해서는 근삿값으로 표현해야 하기 때문에 오차가 생긴다. 이런 문제를 부동소수점 오차라고 한다.( 모든 실수를 8byte, 혹은 12~16byte의 변수에 모두 담을 수 있다고 생각하시는 분은 없겠죠. 변수에 실수를 저장할 때는 어느 정도의 정보 손실이 일어날 수밖에 없습니다. 절대 잊어서는 안되는 것은, 실수 변수는 절대 정확한 값을 가지고 있지 않다는 것입니다. )

ps. 0과 1 사이에도 실수는 무한히 많다....그냥 무한하다. 이 0과 1 사이도 당장 어떻게 정확하게 데이터를 저장해 표현하겠는가.

 

그래서 정확한 연산을 하기 위해서는 정수형으로 데이터를 다루는 것이 좋다. 소수점 연산에 대해서는 % 연산자인 나머지 연산자를 사용하면 된다. 따라서 정수형으로 코드를 수정해 문제를 해결했다.

import java.util.Scanner;

public class Main {
    public static void main(String args[])
    {
        //Float 나 Double을 쓰면 부동소수점으로 인한 오차가 발생하므로 int형을 사용해서만 계산
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int B = scanner.nextInt();
        int V = scanner.nextInt();

        int day;

        if(V<=A)
            day=1;
        else {
            if((V-A)%(A-B)!=0)
                day = (V-A)/(A-B)+2;
            else
                day = (V-A)/(A-B)+1;
        }

        System.out.println(day);
    }
}

 

 

참고

www.acmicpc.net/blog/view/37

부동소숫점 오류