백준 12177번 Dreary Design - C++(cpp) 풀이

 

---

 

1. G-R과 B-G를 고정한다.
2. R, G, B 값이 모두 0 이상 K이하가 되도록 하는 R 값을 모두 구한다.
3. 가능한 모든 (G-R, B-G) 쌍에 대해 1,2를 반복한다.

 

1. G-R과 B-G를 고정한다.

 K 범위가 굉장히 크기 때문에 K 대신 V를 기준으로 생각해준다. 결국 R, G, B 값의 차를 모두 V 이하로 만들어야 한다. G-R 값과 B-G 값을 정하고 나면, R값만 정해도 G, B 값이 저절로 정해진다.

 

2. R, G, B 값이 모두 0 이상 K이하가 되도록 하는 R 값을 모두 구한다.

 1에서 고정한 값을 G-R = i,  B-G = j 라고 하자. 이를 가지고 G와 B를 나타내면, G = R+i, B = R+i+j 이다. R, G, B 값이 모두 0 이상 K 이하여야 하므로, R이 아래의 세 개의 부등식을 만족해야 한다. 순서대로 각각 R, G, B의 범위를 만족하기 위한 부등식이다.

1. 0 ≤ R ≤ K
2. -i ≤ R ≤ K-i
3. -i-j ≤ R ≤ K-i-j

 위의 세 부등식을 만족하는 R 값의 범위는 [max(0, -i, -i-j), min(K, K-i, K-i-j)]이므로, G-R=i, B-G=j 인 경우의 수는 방금 구한 범위의 hi - lo + 1이 된다.

 

 

3. 가능한 모든 (G-R, B-G) 쌍에 대해 1,2를 반복한다. 

 G-R = i,  B-G = j 라고 했을 때, | i | ≤ V와 | j | ≤ V를 만족해야 한다. 또한 R = G-i, B = G+j 이므로, R-B = (G-i) - (G+j) = -(i+j)이다. R값과 B값의 차도 V 이하여야 하므로, |i+j| ≤ V 도 만족해야 한다. 이 세 가지 조건을 만족하는 i, j에 대해 가능한 R 값의 개수를 모두 구해 더해주면 된다.

반응형

---

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

ll V, K;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int T;
    cin >> T;
    
    for (int t=1; t<=T; t++) {
        cin >> K >> V;
        
        ll ans = 0;
        
        // i = G-R, j = B-G
        for (ll i = -V; i <= V; i++) {
            for (ll j = -V; j <= V; j++) {
                if (abs(i + j) > V) continue;   // |R-B| > V
                
                // 1. 0 <= R <= K
                // 2. -i <= R <= K-i (because G = R+i, 0 <= R+i <= K)
                // 3. -i-j <= R <= K-i-j (because B = R+i+j, 0 <= R+i+j <= K)
                ll lo = max((ll)0, max(-i, -i-j));
                ll hi = min(K, min(K-i, K-i-j));
                ans += hi - lo + 1;
            }
        }
        
        cout << "Case #" << t << ": " << ans << "\n";
    }

    return 0;
}