원문 링크
https://www.acmicpc.net/problem/10166

풀이

1차시

• 처음에는 원이니까 각도로 계산하면 되겠거니 했는데.. 실패했다.

  • 예를들어 5/6 이나 1/7 을 소수점으로 더블형태로 표현해 HASHSET 에 넣어서 중복검사를 하려했지만,.. 실패

• 한 한시간 해봤는데, 안되서 곰곰히 생각해보니

  • 1/2000, 2/2000
    : 1/2000 이 소수점으로 0.0005 인데 이정도는 DBL 정밀도가 지원을 할꺼같은데, 안되나보다.
    아무래도 콤퓨터가 소수는 근사치로 표시하다 보니까 이런일이 발생하나보다. 그리고 2000까지 돌리는 와중에 수학적으로는 다르지만, 소수점 오차범위 내에 겹치는 뭔가가 있으면 동작하지 않는 알고리즘인듯 하다.
  • 당연히 대충 빨리 끝낼려고 소수점 오차범위가 모자라? 그러면 *10000 정도 해서 늘려주지! 했는데, 실패였다..

2차시

• 살짝 다른분들 코드를 살펴보니 boolean 배열을 만들어서 중복체크를 빠르게 수행한다. 배열인덱스로 원소접근은 항상 제일 빠른 연산이니 좋은듯 해서 아이디어만 구하고 바로 코딩하니까 성공..

결론

• 컴퓨터에서 소수점으로 비교(값이 같은지) 연산 같은거 하지말자.. hash에 넣고 중복제거되길 바라는것도 비교연산이다..
  : 아무래도 프리미티브 타입이니 내부적으로 equals 함수에서 동일한지 "=" 연산을 수행할 듯 하다

import java.util.HashSet;
import java.util.Scanner;
// Main
class Solution {


    final static int MAXI = 2001;
    final static boolean[][] map = new boolean[MAXI][MAXI];
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int a,b,ans = 0;
        a = sc.nextInt();
        b = sc.nextInt();

        for(int i=a ; i<=b ; i++) {
            for(int j=1 ; j<=i ; j++) {

                int gcd = getGcd(i,j);
                int x = i/gcd;
                int y = j/gcd;

                if(map[x][y] == false) {
                    ans++;
                    map[x][y] = true;
                    //System.out.printf("n=%d ,  currnet= %d/%d \n",i,x, y);
                }
            }


        }

        System.out.println(ans);


    }


    private static int getGcd(int a, int b) {
        if (b == 0) return a;
        return getGcd(b, a%b);
    }


}

class Couple {
    int x;
    int y;
    Couple(int x,int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        Couple solo = (Fair)obj;
        if(fair.x == this.x) {
            if (fair.y == this.y) {
                return true;
            }
        }
        return false;
    }


}

참고로

• Couple 클래스는 c++ 에 make_fair 기능 구현을 위해 만들었는데 equals 메서드 오버라이드해서 비교연산 하려고 했는데 생각대로 동작하지 않아 드롭

오늘 저녁 이거 한문제 붙잡고 있는다고 까먹었다 ㅋㅎ... 알고리즘은 역시 30분 잡아보고 모르면 답을 보는게 베스트인거 같다.

• 근데 공돌이들은 best prectice 를 알면서, Anti pattern 인줄 알면서 꼭 하지말란대로 한다. ㅋㅎ..