백준: Gold5④ - 1188, 1405, 1461

</br> 계속 계속
</br>

1188: 음식 평론가

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

소세지를 사람 수만큼 똑같이 최소의 칼질로 나누기

방법 1.

    n %= m;
    if( n == 0 ){
        cout << 0 << endl;
        return 0;
    }
    int num = 1, k = 0;
    for(int i = 1; i <= n*m; i++){
        s[i] = num;
        if( ++k == n ){
            k = 0;
            num++;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n*m; i += m){
        cnt += s[i+m-1] - s[i];
    }
    cout << cnt << endl;

사람 수보다 많으면 일단 온전한 채로 나눠주고, 남는 것들을 잘라야 하므로 n %= m;한다. 만약 나머지가 없다면 이미 딱 떨어졌으므로 종료한다.
이후, 소세지 자르기를 시뮬레이션…했다.

ex) 소세지 2개, 평론가 5명
i 1 2 3 4 5    6 7 8 9 10
p 1 1 2 2 3    3 4 4 5 5

1. i == 1: s[i+m-1] - s[i] 결과 3 - 1 = 2이므로 2번 잘라야 함.
2. i == 2: s[i+m-1] - s[i] 결과 5 - 3 = 2이므로 2번 잘라야 함.
따라서 총 4번

이렇게 하니까 맞긴 맞더라!!
근데 다른 풀이를 검색해 보니 더 똑똑한 방식이 있다고 한다
</br>

방법 2.

    cout << m - gcd(n, m) << endl;

답이 m에서 n과 m의 최대공약수를 뺀 것이라 한다.

https://www.acmicpc.net/board/view/15979
여기 설명이 아주 잘 되어 있다.
즉 소세지를 전부 이어 붙이고 자른다 치면, 각 크기가 n/m이 될 거다.
이걸 t명이 가져가면 t*(n/m)이 된다(t <= m).
그런데 이 (t*n)/m이 자연수가 되는 경우, 소세지를 자르지 않아도 된다. 따라서 전체 경우 m에서 (tn)/m이 자연수가 되는 경우의 수를 빼주면 되는데, n과 m의 최대공약수를 k라 하면 (tn)/m = (tn/k)/m/k = (tQ)/Q’(Q와 Q’는 서로소)이고, 따라서 t가 Q'의 배수일 때를 세면 된다. 이 경우의 수는 총 m/Q'개이다. 즉 m - m/Q’를 구해야 하는데, Q’ = m/k이므로 식은 m - m/m/k = m - k`가 되므로 이걸 바로 구하면 끝

대단해~~
</br>

1405: 미친 로봇

https://www.acmcpc.net/problem/1405

로봇이 동서남북으로 확률 따라 n번 움직일 때, 지나간 곳을 다시 지나가지 않을 확률

void func(int x, int y, int d, double now){
    if( d == n ){
        ans += now;
        return;
    }
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if( visited[nx][ny] == 0 ){
            visited[nx][ny] = 1;
            func(nx, ny, d+1, now*p[i]);
            visited[nx][ny] = 0;
        }
    }
}

dfs로 찾을 수 있다.
방위를 선택할 때마다 해당 확률을 곱해주며 넘어간다. 만약 n번 시행되었다면 성공했으므로 답에 더해준다.
</br>

1461: 도서관

https://www.acmcpc.net/problem/1461

최소로 움직여서 책 정리하기

int func(vector<int> &v){
    int ret = v[v.size()-1];
    int k = min(m, (int)v.size());
    while( k-- ){
        v.pop_back();
    }
    return ret;
}

// in main()
    sort(vp.begin(), vp.end());
    sort(vm.begin(), vm.end());
    int ans = 0;
    if( vp.size() == 0 && vm.size() == 0 ){
        cout << 0 << endl;
        return 0;
    }
    else if( vp.size() == 0 ) ans += func(vm);
    else if( vm.size() == 0 ) ans += func(vp);
    else if( vp[vp.size()-1] > vm[vm.size()-1] ) ans += func(vp);
    else ans += func(vm);
    while( vp.size() || vm.size() ){
        if( vm.size() == 0 ) ans += 2*func(vp);
        else ans += 2*func(vm);
    }
    cout << ans << endl;

그리디 문제다. 일단 가장 긴 거리는 다시 돌아오지 않아야 하므로 마지막에 옮겨야 한다. 코드에선 미리 처리해서 더했다.

ex)
7 2
-37 2 -6 -39 -29 11 -28

정렬 후:
-39 -37 -29 -28 -6  0  2 11

가장 긴 걸 뺀 후:
        -29 -28 -6  0  2 11
        (2개 옮길 수 있으므로)

이후엔 그냥 갈 수 있는 대로 끝에서부터 처리하며 가면 된다.

ex)
-29 -28 -6  0  2 11
        -6  0  2 11
        -6  0
            0 
            (어느 쪽을 먼저 갈 지 순서는 상관 없음 무조건 다 가야하니까)

적고 보니 어차피 인덱스만 중요하므로 연산에 시간이 걸리는 pop_back()을 굳이 할 필요 없이 m번째에 맞는 인덱스들을 더해주기만 해도 될 것 같다.
</br>

---

열심히 하자~~
</br>