[Baekjoon - 3566] 대형 스크린

난이도: Bronze II

 

태그

• Mathematics
• Brute Force

 

풀이

1. 창고 속 모니터로 대형 모니터 만들기 (방향 회전 불가)

목표로 하는 대형 모니터의 크기를 \( S_{y}, S_{x} \)로, 해상도를 \( R_{y}, R_{x} \)로 나타내봅시다.

그리고, 우리가 사용할 창고 속 모니터는 크기 \( s_{y}, s_{x} \), 해상도 \( r_{y}, r_{x} \), 가격 \( p \)로 나타내보죠.

 

회전이 불가능하니, 하나의 모니터를 크기/해상도 조건이 만족될 때까지 가로/세로로 계속 붙이는 수밖에 없습니다.

그럼, 세로축으로 붙이게 되는 개수와 가로축으로 붙이게 되는 개수만 알면, 필요한 가격 역시 알 수 있겠죠.

 

세로축으로 붙이게 되는 개수 \( c_y \) = max(크기 조건을 만족시키기 위해, 해상도 조건을 만족시키기 위해) 붙여야 하는 모니터의 개수 = \( \max \left( \left\lceil \frac{S_y}{s_y} \right\rceil, \left\lceil \frac{R_y}{r_y} \right\rceil \right) \)가 됩니다.

가로축으로 붙이게 되는 개수 \( c_x \) 역시 비슷한 과정을 거치면, \( \max \left( \left\lceil \frac{S_x}{s_x} \right\rceil, \left\lceil \frac{R_x}{r_x} \right\rceil \right) \)가 되죠.

 

남은 건, 이 때 필요한 가격 = \( c_y \times c_x \times p \)까지 계산해준 뒤, 이 가격이 가장 작은 모니터를 선택해주면 됩니다.

 

2. 창고 속 모니터로 대형 모니터 만들기 (방향 회전 가능)

방향 회전이 가능하다고 해도, 90도로 돌리는 것만 생각해보면 됩니다.

 

모니터를 90도 회전시키면, 가로와 세로가 바뀌겠죠.

그러니, [1]의 식을 (가로, 세로)의 경우와 (세로, 가로)의 경우에 대해 계산하고, 최솟값을 구하면 됩니다.

 

3. 코드

void Main(){
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    ll ans = 1e18;
    int n; cin >> n; while (n--){
        int x3, y3, x4, y4; ll p; cin >> x3 >> y3 >> x4 >> y4 >> p;
        int x = max((x1+x3-1)/x3, (x2+x4-1)/x4);
        int y = max((y1+y3-1)/y3, (y2+y4-1)/y4);
        //cout << p << ' ' << x << ' ' << y << endl;
        ans = min(ans, p*x*y);
        swap(x3, y3); swap(x4, y4);
        x = max((x1+x3-1)/x3, (x2+x4-1)/x4);
        y = max((y1+y3-1)/y3, (y2+y4-1)/y4);
        //cout << p << ' ' << x << ' ' << y << endl << flush;
        ans = min(ans, p*x*y);
    }
    cout << ans;
}