먼저 곱하고 나중에 나눠줄까, 먼저 나누고 나중에 곱해줄까?(백준/1072)

튜터로 학생들의 알고리즘 코드를 봐 주다가 다음 문제를 마주쳤다.

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

 

문제만 본다면 평범한 알고리즘 문제이지만, 다음 과정에서 문제가 있었다.

백준은 어떤 부분이 틀렸는가에 대해 제공하지 않기에 학생들은 스스로 반례 또는 틀린 코드를 찾고 있다가, 어느 코드가 틀린지 몰라 나에게 도움을 얻으러 왔다.

나도 분명히 이분탐색 로직에는 문제가 없는것 같아 어느 부분에서 틀렸지 찾다가, 다음을 바꿔보니 맞는 코드가 되었다.

int percentage1 = (int)((double)x * 100 / y);
int percentage2 = (int)((double)x / y * 100);

어떤 수식이 틀렸고, 어떤 수식이 맞을까?

부동소수점 이슈는 소수점 계산할 때 항상 나오는 이슈라 항상 알고는 있지만, 실제로 문제를 복기하며 무엇이 틀렸는지 찾을때는 부동소수점 이슈를 발견하기가 굉장히 어렵다.

마치 long type을 써주지 않아 overflow가 났을 때처럼.

일단, 문제를 해결하기 위해 어느 부분에서 문제가 터졌는지 확인하기 위해 살짝 코드를 짜 보았다.

public class Main {
    public static void main(String[] args) throws IOException {
        for (int x=0; x<100; x++){
            for (int y=1; y<100; y++){
                int z1 = (int)((double)x * 100 / y);
                int z2 = (int)((double)x / y * 100);
                if (z1 != z2 && x < y){
                    System.out.println("z1 = " + z1);
                    System.out.println("z2 = " + z2);
                    System.out.println("x = " + x);
                    System.out.println("y = " + y);
                }
            }
        }
    }
}

x와 y를 변환시켜 주면서, 위의 두 수식이 달라질 때를 찾았다.

그리고, 다음 결과를 발견할 수 있었다.

z1 = 58
z2 = 57
x = 29
y = 50

x = 29, y = 50일 때, z1는 58%를, z2는 57%를 반환했다.

정확하게 보기 위해 z1과 z2를 double로 바꾸었더니, x=29, y=50에 대해 다음을 반환했다.

z1 = 58.0
z2 = 57.99999999999999

상식상 29/50은 58%가 되어야 하기에, z1이 맞는 수식임을 알 수 있다.

따라서, 퍼센테이지를 나타낼 때 분자를 크게 가져가야만 소숫점을 잘 출력하는 것을 알 수 있다.

분자가 더 큰 경우에도 마찬가지다.(x>y)

9900가지 경우 중 39건의 경우에서 다른 결과를 반환했다.

이 경우에도 z1이 z2에 비해 조금 더 정확한 결과를 도출해 냄을 알 수 있다.

따라서 결과는 다음과 같다.

퍼센테이지 등의 결과를 도출해 낼 때에는, 항상 분자를 크게 가져가는것이 조금 더 정확하다.

글을 쓰다보니 사실 어떻게 생각해보면 당연한 결과긴 하지만, 그래도 오랜만에 한번 짚고 넘어갈 문제라 포스팅을 해 보았다.