[AtCoder - Diverta2019 B] RGB Boxes

난이도: 538

 

태그

• Counting
• Brute Force

 

풀이

1. 순서쌍에 대해 생각해보기.

\( r, g \)가 고정되었다고 해봅시다. 이 때, 가능한 \( b \)의 개수는 얼마나 될까요?

\( rR + gG + bB = N \)을 만족시켜야 하는데, \( b \)를 제외하고는 모두 고정된 값이니

가능한 값은 1가지이거나 0가지가 됩니다.

 

즉, \( r, g \)에 대해서만 브루트포스를 하면서 \( b \)의 가능성 여부를 따지면 되겠죠.

 

2. \( r, g \)가 고정될 때, 가능한 \( b \)가 존재하는 경우는?

\( rR + gG + bB = N \)라는 식을 약간 변형해서, \( b \)만 우변에 남겨봅시다.

\( b = \frac{N - rR - gG}{B} \)

 

즉, \( N - rR - gG \)가 \( B \)의 배수인지 여부로 판별하면 됩니다.

 

3. 정리

그러니, \( O(N^2) \)으로 \( r, g \)에 대해 브루트 포스를 돌리면서 가능한 \( b \)가 존재하는지 확인하고,

존재할 때마다 답에 1을 더해주면 됩니다.

 

4. 코드

void Main(){
    int r, g, b, n; cin >> r >> g >> b >> n;
    int ans = 0;
    for (int cr = 0; r*cr <= n; cr++){
        for (int cb = 0; r*cr + b*cb <= n; cb++){
            int num = n - r*cr - b*cb;
            if (num%g != 0){ continue; }
            ans += 1;
        }
    }
    cout << ans;
}