[알고리즘 문제풀이] 기타 코딩테스트 1-2

 

문제 : 

피시방은 시간당 1,000원으로 이용할 수 있으며 매일 h 시간 동안 p 대의 PC를 운영하고 있다.

피시방은 인기가 많아 예약제로 운영되며 미리 고객들로부터 사용을 희망하는 PC번호와 사용 희망 시간을 전달받아 운영하고있다.

예를 들어 2대의 PC를 활용하여 하루 4시간 동안 영업을 한다고 가정하고 총 7명의 손님으로부터 아래와 같은 예약을 받았을 때 1번 PC를 통해 0원, 2번 PC를 통해 4,000원의 이익을 얻을 수 있다.

예약 PC 사용 희망 시간
1번 10시간
1번 5시간
1번 7시간
2번 10시간
2번 1시간
2번 3시간
2번 7시간

피시방의 상세 조건은 아래와 같다.
- 고객이 운영 시간보다 사용 희망 시간을 많이 신청한 경우 해당 고객은 받지 않는다.
- 고객은 한 시간 단위로 사용 희망 시간을 신청한다.
- 각 PC당 얻을 수 있는 최대 수익을 출력하시오.

 

 

입력 : 

첫 번째 줄에는 PC의 대수 p, 예약한 손님의 수 n, 피시방 운영 시간 h 순으로 공백을 구분자로 입력받는다. (p, n, h는 정수이다.)
1≦p≦100
0≦n≦1000
0≦h≦24
두 번째 줄부터 n+1번째 줄까지 예약한 손님이 이용할 PC번호 정수 x와 이용할 시간 정수 y를 공백을 구분자로 입력받는다.
1 ≦ x ≦ p
0 ≦ y ≦ ∞

 

ex)

2 7 4
1 10
1 5
1 7
2 10
2 1
2 3
2 7

 

 

 

출력 :

PC번호와 각 PC를 통해 소마가 얻을 수 있는 최대 수익을 공백을 구분자로 출력한다.
PC번호를 기준으로 순서대로 출력한다.
PC번호는 1부터 시작하며 p 번 까지 있다.

 

ex)
1 0
2 4

 

 

 

풀이 및 코드 : 

 

#include <iostream>

using namespace std;
    
int p = 0; //피씨 대수
int n = 0; //손님 명수
int h = 0; //h시간만 운영할거다
int dp[105][25]; //그냥 넉넉하게

void solution() {
    for (int i = 1; i <= p; i++) //dp의 초기값 지정
        dp[i][0] = 1;

    while (n--) { // n만큼 돌면서 dp 수행
        int x, y; //입력받을거
        cin >> x >> y;
        for (int j = h; j >= y; j--) {
            dp[x][j] |= dp[x][j - y];
        }

    }
    int ans = 0;

    for (int i = 1; i <= p; i++) {
        for (int j = h; j >= 0; j--) {
            if (dp[i][j]) {
                ans += j;
                cout << i << '\0' << j << endl;
                break;
            }
        }
    }
}

int main() {
    cin >> p >> n >> h;
    solution();
    return 0;
}