백준: Silver1① - 1011, 1041, 1052

</br> 실버 1이 되었다!! 현재 657인데, 문제 풀 때마다 10이나 11 정도 오르고 골드 5까지는 143 남았으니까 14문제 정도일 것 같다.
</br>

1011: Fly me to the Alpha Centauri

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

우주선 속도 조절을 1씩 밖에 못할 때 이동하기

</br>

    for(int i = 0; i < t; i++){
        int x, y;
        cin >> x >> y;
        y -= x;
        int l = 0, h = INT_MAX;
        long long a;
        while( l <= h ){
            a = (l+h) / 2;
            if( a*(a+1) < y && y <= (a+1)*(a+2) ){
                break;
            }
            else if( y <= a*(a+1) ){
                h = a;
            }
            else{
                l = a;
            }
        }
        int rem = y - a*(a+1);
        if( rem <= a+1 ){
            cout << a*2 + 1 << endl;
        }
        else{
            cout << a*2 + 2 << endl;
        }
    }

생각해내는데 꽤 걸렸다…
일단 x와 y를 입력 받는데, 계산이 편하게 두 차만 y에 저장한다. 출발할 때도, 도착할 때도 속도가 1이어야 한다는 제약이 있다.
그래서 한 번 적어 보니

1 2 ... a     k     a ... 2 1

배열은 다양하게 나오겠지만, 가장 기본적인 속도 배열이 위와 같이 될 거다.
저 k를 어떻게 처리할까 생각하니, 모자라면 옆에서 들고 오고 넘치면 반으로 나눠 주면 되겠다 싶더라.

ex)
1 ... 98 99    1    99 98 ... 1
의 경우 옆에서 1씩 주고 주고 하다 보면 고르게 정리될 거고

1 ... 98 99    201    99 98 ... 1
의 경우 반으로 나눈 다음 옆에서 1씩 주고 주고 하다 보면 고르게 정리될 거임

그래서 저 a를 구하는 게 문제였는데, 입력 범위가 2^31 - 1 까지다 보니 구하는 데에 오래 걸려서 이분 탐색을 사용하기로 했다.

다행히도 정답 휴
</br>

1041: 주사위

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

    +---+        
    | D |        
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
    | C |        
    +---+   

해당 전개도로 만든 주사위를 쌓아 n*n*n 정육면체를 만들 때, 보이는 면의 최소 합

    if( n == 1 ){
        cout << a+b+c+d+e+f - max({a, b, c, d, e, f}) << endl;
        return 0;
    }

    int minSum1 = min({a, b, c, d, e, f});
    int minSum2 = min({a+b, a+d, a+e, a+c, b+d, d+e, e+c, c+b, f+b, f+d, f+e, f+c});
    int minSum3 = min({a+b+d, a+d+e, a+e+c, a+c+b, f+b+d, f+d+e, f+e+c, f+c+b});

    ull ans = (ull)4 * minSum3
            + ((ull)(n-2) * 8 + 4) * minSum2
            + ((ull)(n-2) * (n-2) * 5 + (ull)(n-2) * 4) * minSum1;

    cout << ans << endl;

초등학교 때 이런 문제 푼 거 같은데 왜 여기 있을까
n이 1이면 그냥 주사위 하나이므로, 가장 큰 수가 바닥에 있다고 보면 된다.
그게 아니라면, n 정육면체의 맨 위 꼭짓점 4개는 주사위의 3면이 나오고, 모서리들과 바닥의 꼭짓점 4개는 2면이 나오고, 나머지는 1면씩 나온다.
별 거 없고 오버플로우가 일어날 수 있으니 형변환을 해 주면 끝
</br>

1052: 물병

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

물병 합쳐서 원하는 개수로 만들기

    bottle[1] = n;
    int now = n;
    int cnt = 0;
    while( now > k ){
        bool b = true;
        for(int i = 0; i < n; i++){
            if( bottle[i] >= 2 ){
                int q = bottle[i] / 2;
                if( now - q >= k ){
                    bottle[i] %= 2;
                    now -= q;
                    bottle[i+1] += q;
                }
                else{
                    q = now - k;
                    now -= q;
                    bottle[i+1] += q;
                }
                b = false;
            }
            if( now == k ) break;
        }
        if( b ){
            for(int i = 0; i < n; i++){
                if( bottle[i] ){
                    cnt += pow(2, i-1);
                    bottle[i]--;
                    bottle[i+1]++;
                    break;
                }
            }
        }
    }
    cout << cnt << endl;

처음엔 그냥 생각난 대로 하나씩 합치다 모자라면 1씩 더하기 했는데 시간 초과가 나더라
bottle[i]에 i번째 합쳐진 물병들의 개수를 저장한다.
물병 개수가 2개 이상이면 합칠 수 있는 만큼 합친다.
만약 다 검사했는데 합칠 수 있는 물병이 없다면 존재하는 가장 작은 i번째를 찾아서, 물병을 2^(i-1)개 추가해 주면 된다.
</br>

---

골드를 향하여
</br>