백준: Silver3② - 1072, 1124, 1141, 1166, 1198

</br> 실버 3 문제들 이어서 계속~
</br>

1072: 게임

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

게임 승률 1프로 올리기

    int z = (100*y) / x;

    if( z >= 99 ){
        cout << -1 << endl;
        return 0;
    }

    int ans = 0;
    int l = 0, h = 1000000000;
    while( l <= h ){
        int mid = (l + h) / 2;

        if( 100*(y + mid) / (x + mid) <= z ){
            ans = mid+1;
            l = mid+1;
        }
        else{
            h = mid-1;
        }

    }
    cout << ans << endl;

100*(y + k) / (x + k)로 승률을 구할 수 있다.

하나 씩 찾으면 당연히 시간 초과 나므로 이분탐색을 사용한다.
참고로 여기서 범위가 1 ≤ X ≤ 1,000,000,000 이므로 x, y를 long long을 사용해 줘야 함…
</br>

1124: 언더프라임

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

수를 소인수분해해서 나온 소수들의 개수가 소수인 수가 언더프라임

    isPrime[0] = -1;
    isPrime[1] = -1;
    for(int i = 2; i < b+1; i++){
        if( isPrime[i] != -1 ){
            primes.push_back(i);
            isPrime[i] = 1;
            for(int j = 2; i*j < b+1; j++){
                isPrime[i*j] = -1;
            }
        }
    }

일단 소수 나오면 바로 이렇게 에라토스테네스의 체로 dp 구하기.

이번엔 일단 풀어 봤는데 시간이 꽤 걸리길래 다른 방식으로도 풀어 봤다.

방법 1

    int ans = 0;
    for(int i = a; i < b+1; i++){
        int k = i, cnt = 0;
        for(int j = 0; primes[j] <= k && j < primes.size(); j++){
            while( k % primes[j] == 0 ){
                cnt++;
                k /= primes[j];
            }
        }
        if( isPrime[cnt] == 1 ){
            ans++;
        }
    }
    cout << ans << endl;

말 그대로 수가 있으면 소수로 쪼개면서 카운트하고, 그 카운트를 다시 소수인 지 확인해 주었다.
ex) 12 = 2 * 2 * 3

방법 2

int func(int k){
    if( isPrime[k] == 1 ){
        return 1;
    }
    else if( k%2 == 0 ){
        return func(k/2) + 1;
    }
    else{
        for(int j = 0; primes[j] <= k && j < primes.size(); j++){
            if( k % primes[j] == 0 ){
                return func(k/primes[j]) + 1;
            }
        }
    }
}

// in main()
    int ans = 0;
    for(int i = a; i < b+1; i++){
        int k = i, cnt = 0;

        if( isPrime[func(k)] == 1 ) ans++;
    }
    cout << ans << endl;

하지만 잘 생각해 보면

1. 수가 소수인 경우 무조건 카운트는 하나
2. 짝수인 경우 카운트는 n/2에 더하기 1
3. 홀수인 경우도 어떤 k에 의해 나누어지므로 n/k에 더하기 1

이므로 해당 함수를 짜서 돌려 보니 시간이 훨씬 단축 되었다.

방법 1은 308ms, 2는 8ms가 나왔다.
</br>

1141: 접두사

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

단어들 집합을 받고, 접두사가 없는 가장 큰 부분 집합 크기 구하기

    sort(v.begin(), v.end());

    for(int i = 1; i < v.size(); i++){
        bool b = true;
        for(int j = 0; j < v[i-1].size(); j++){
            if( v[i-1][j] != v[i][j] ){
                b = false;
            }
        }
        if( b ){
            v.erase(v.begin() + i-1);
            i--;
        }

    }
    cout << v.size() << endl;

입력 받아서 정렬해 주면 짧고 간단한 것일 수록 앞에 간다.
따라서 앞의 녀석과 비교해서 걔가 내 접두사가 되면 걔를 없애 버리면 됨.
남은 것들이 최대의 부분 집합이다. 싶어서 해 봤는데 잘 된다.

ex) run, runi, runrun과 같을 경우 run이 runi의 접두사니까 없애 버리면 됨 정렬하면 run, riii, runrun 같은 일은 없으니까 되는 게 맞다
</br>

1166: 선물

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

하나의 직육면체에 정육면체를 n개 넣는데, 그 정육면체 한 변의 길이의 최대 구하기

    double a = 0.0, low = 0.0, high = min({l, w, h});

    for(int i = 0; i < 10000; i++){
        long double mid = (low+high) / 2.0;
        if( ((long long)(l/mid))*((long long)(w/mid))*((long long)(h/mid)) < n ){
            high = mid;
        }
        else{
            low = mid;
        }
    }

    cout << low << endl;

얘도 이분탐색이다. 알고리즘은 바로 생각나고 어려울 게 없는데, 자료형 때문에 애 좀 먹었다…
</br>

1198: 삼각형으로 자르기

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

문제가 말이 많은데 그냥 점 3개 골라서 삼각형 넓이가 가장 큰 거 구하기.
그림 좀만 그려 보면 바로 앎

    for(int i = 0; i < n-2; i++){
        for(int j = i+1; j < n-1; j++){
            for(int k = j+1; k < n; k++){
                ans = max( ans, abs(x[j]*y[i] + x[k]*y[j] + x[i]*y[k] - x[i]*y[j] - x[j]*y[k] - x[k]*y[i]) );
            }
        }
    }

    cout << (double)ans / 2.0 << endl;

간단하게, 조합으로 3개를 골라서 signed area로 넓이를 구한다.(2배 된 상태)
그리고 출력할 때 2로 나눠서 보내면 됨.

무슨 오차를 10^-9까지 허용한다는데 어차피 정수 좌표들이라 .5 단위로 나온다.
그런데… 계속 오답 처리 돼서 뭐지 했는데, 이상하게도 같은 코드인데 cout.precision(11);을 넣고 double 타입으로 하니까 정답 처리 된다.
채점 방식이 어떻게 되는 건지는 모르겠음.
</br>

---

풀다 보니 또 실버 2가 되었다.
다음은 실버 2 문제들~~
</br>