백준#1206 사람의 수(java)

전체 코드

  import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        new Sol();
    }
}
class Sol{
    Buf buf = new Buf();
    int N;
    int[] input;

    public Sol(){
        N = buf.readInt();
        input = new int[N];
        for (int i = 0; i<N; i++){
            String input = buf.read();
            int idx = input.indexOf(".");
            this.input[i] = Integer.parseInt(input.substring(idx+1));
        }
        int n=0;
        while(true){
            n++;
            int result = 0;

            for (int i = 0; i < N; i++){
                if ((input[i] * n)%1000==0||(1000-n)<(input[i]*n%1000))result++;
                else break;
            }
            if (result == N)break;;
        }
        System.out.println(n);
    }
}
class Buf{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = null;

    public String read(){
        while(st == null || !st.hasMoreTokens()){
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                return null;
            }
        }
        return st.nextToken();
    }

    public Integer readInt(){
        return Integer.parseInt(read());
    }

    public float readFloat(){
        return Float.parseFloat(read());
    }
}

풀이

이 문제의 핵심은 부동소수점이다. 실수상태에서 처리하게되면 부동소수점 오차가 발생하여 문제가 발생한다. 따라서 입력값에 1000을 곱하더라도 해당 곱하는 과정에서 또 오차가 발생하여 테스트 케이스 약 8%부분에서 오류가 발생한다.
최종적으로 입력값을 String으로 받고 소수점밑을 subString한 다음 int형으로 전환해주니 정답이였다.

우선 풀이과정은 다음과 같다.

각 항에 mod 1 즉 % 1을 해주면 x는 자연수 이므로 0이 된다.

이후 k*y mod 1을 넘기고 모듈러 특성으로 인해 다음과 같이 표현된다.

이때 k는 소수점 3자리 밑이므로 0.001 미만이다. 즉 k*y < 0.001*y 이를 위의 식에서 정리하면 다음과 같다.

이 것과 a[i]에서 바로 나누어 떨어지는 a[i] * y mod 1 == 0 경우를 고려하면 브루트포스로 y를 구할 수 있다. 수식으로 써보겠다고 이상하게 되었지만 결국 브루트포스 문제였다.

문제는 부동 소수점

for (int i = 0; i<N; i++){
            String input = buf.read();
            int idx = input.indexOf(".");
            this.input[i] = Integer.parseInt(input.substring(idx+1));
}

부동 소수점 오차를 위해 필요없는 정수 부분을 substring으로 지워버리고 소수만 가져와 계산했다.

for (int i = 0; i < N; i++){
                if ((input[i] * n)%1000==0||(1000-n)<(input[i]*n%1000))result++;
                else break;
            }

그에 맞게 1000씩 곱해주면서 모든 평균값이 참인지 확인했다.