[백준 3566번] 대형스크린

문제 설명

상근이는 모니터를 여러개 붙여서 대형 모니터를 만드는 일을 하고 있다.

고객은 대형 모니터의 가로, 세로 해상도(픽셀)과 가로 세로 크기(밀리미터)를 상근이에게 주문한다. 상근이는 고객의 주문 값보다 크거나 같은 해상도, 크거나 같은 크기의 대형 모니터를 만들어야 한다. 이때, 제조비가 최소가 되어야 한다.

대형 모니터는 항상 같은 종류의 모니터로 만들어야 한다. 대형 모니터의 해상도, 크기는 모니터를 붙인 형태로 각각을 더하면 되고, 가격은 사용한 모니터의 가격의 합이다.

상근이의 창고에는 모니터가 여러 종류가 있고, 각각의 해상도와 크기, 가격은 모두 알고 있다. 모니터를 회전 시켜서 대형 모니터를 만들 수 있다. 하지만, 대형 모니터에 포함된 모니터는 모두 같은 방향이어야 한다. 상근이는 모니터를 매우 많이 가지고 있어, 필요한 만큼 사용할 수 있다.

입력

첫째 줄에 대형 모니터의 가로 세로 해상도, 가로 세로 크기 r_h, r_v, s_h, s_v가 주어진다. 각 값은 100보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

다음 줄에는 상근이가 가지고 있는 모니터 종류의 개수 n이 주어진다. (1 ≤ n ≤ 100)

다음 n개 줄에는 각 모니터의 가로 세로 해상도, 가로 세로 크기, 가격 r_h,i, r_v,i, s_h,i, s_v,i, p_i 가 주어진다. 이 값도 모두 100보다 크거나 같고, 10,000보다 작거나 같다.

출력

첫째 줄에 대형 모니터를 만드는 가격 중 가장 저렴한 가격을 출력한다.

접근 방식 및 풀이

최저 가격을 구하려면 모든 모니터마다 비용을 계산해서 제일 낮은 값을 선택해야한다.

예를 들어 A 모니터를 사용했을 때 소비될 비용을 구하기 위해선 대형 모니터를 만들기 위해 필요한 A 모니터 개수가 필요하다. 총 비용 = 필요한 모니터 개수 * 해당 모니터 하나의 가격 이기 때문이다.

여기서 필요한 모니터 개수는 세로에 필요한 모니터 개수와 가로에 필요한 모니터 개수를 구해서 곱하면 된다. 그럼 세로에 필요한 모니터 개수와 가로에 필요한 모니터 개수는 어떻게 구할까? 세로와 가로에 대해 계산하는 방법은 동일하기 때문에 세로로 예를 들어보자.

세로에서 화면 해상도와 화면 크기를 둘 다 만족해야 한다. 그래서 만약 A 모니터 5개로 화면 해상도를 만족할 수 있다고 해도 화면 크기를 만족하기 위해서 10개가 필요하다면 결국 10개를 사용해야한다.

같은 방식으로 가로에 필요한 모니터 개수도 구하면 된다.

코드

문제 풀이에 사용한 언어: C

#include <stdio.h>
#include <math.h>

int monitor_num, rh, rv, sh, sv, rhi, rvi, shi, svi, pi, result = 2147483647, tem;

// 두 숫자 중 더 높은 숫자 리턴.
int max(int a, int b){
    return a > b ? a : b;
}

// 두 숫자 중 더 낮은 숫자 리턴.
int min(int a, int b){
    return a < b ? a : b;
}

// 특정 모니터를 사용할 때 소비될 총 비용.
int calculate(int a, int b, int c, int d, int price){
    int highest_h, highest_v;
    
    // 세로 화면 해상도, 세로 화면 크기를 만족시키기 위해 필요한 모니터 개수.
    highest_h = max(ceil((double)rh / a), ceil((double)sh / c));
    
    // 가로 화면 해상도, 가로 화면 크기를 만족시키기 위해 필요한 모니터 개수.
    highest_v = max(ceil((double)rv / b), ceil((double)sv / d));
    
    // 총 비용 = 가로로 필요한 모니터 개수 * 세로로 필요한 모니터 개수 * 모니터 하나당 비용
    return highest_h * highest_v * price;
}

int main(){
    
    scanf("%d %d %d %d", &rh, &rv, &sh, &sv);
    scanf("\n%d", &monitor_num);
    
    for(int j = 0; j < monitor_num; j++){
        scanf("\n%d %d %d %d %d", &rhi, &rvi, &shi, &svi, &pi);
        
        // 기본 상태로 계산한 비용, 가로 세로를 바꿔서 계산한 비용,
        // 지금까지 구한 비용 중 최저 비용 중 가장 낮은 것으로 선택해서 최저 비용을 업데이트.
        result = min(result, min(calculate(rhi, rvi, shi, svi, pi), calculate(rvi, rhi, svi, shi, pi)));
    }
    
    printf("%d\n", result);
    return 0;
}