문제
루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.
각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?
루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.
제약조건
- 1 ≤ N ≤ 106인 정수
- 1 ≤ W ≤ 104인 정수
- 1 ≤ Mi, Pi ≤ 104인 정수
입력형식
첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.
출력형식
첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.
90 1
70 2
알고리즘 정리
W : 최대무게 N : 몇개의 귀금속이 있나 M : 금속 무게 P : 가격
가격이 가장 높은 줄의 무게 순으로 정렬 종류만큼 배열 크기 1000000
전부 무게0, 가격0 초기화
for(갯수만큼) i 인덱스 가격비교
더크면 i 무게0, 가격0 = 넣기
temp 필요
for(배열크기만큼) 가격비교 담겨있는게 작으면 i번째 담겨 있는거 temp 빼기, 넣고, 비교값에 temp 값 넣기
템프가격이 0이면 break; 아니면 다음
result =0;
while(최대 < 0)
남은무게 = W - M check 최대보다 넘나?(남은무게 < 0)
- 최대(or 남은무게) / M * 가격(x[조정가격] = 최대 X 가격/(금)무게) : result + 가격 안넘어
- result += 가격
- 최대(or 남은무게) / M * 가격 => -> 남은 무게, 누적가격 남은무게 - M2
코드
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define WEIGHT 0
#define PRICE 1
int main(int argc, char** argv)
{
unsigned int W; // 배낭무게
unsigned int N; // 귀금속의 종류
unsigned int M; // 금속무게
unsigned int P; // 가격
unsigned result = 0; // 최대 가격
//input 받기
cin >> W >> N ;
//cout << W << " " << N << endl;
vector<vector<int>> M_P; //무게, 가격
vector<int> v;
for(int d=0; d < N ;d++)
{
cin >> M >> P;
M_P.push_back(v);
M_P[d].push_back(M);
M_P[d].push_back(P);
}
int data[N][2]; //0: 무게, 1:가격
//int data[10000]; //가격은 배열의 index, 무게는 해당 배열의 값
memset(data, 0x00, sizeof(data));
//cout << data[N-1][0] << " " << data[N-1][1] << endl;
int compare_p =0, compare_w=0, temp_price = 0, temp_weight=0;
for(int i=0 ; i < N ; i++){
compare_p = M_P[i][PRICE];
compare_w = M_P[i][WEIGHT];
for(int j=0 ; j < 1000000 ; j++){
if(data[j][PRICE] < compare_p)
{
//cout << "before data " << data[j][PRICE] << " compare_p " << compare_p << endl;
temp_price = data[j][PRICE];
temp_weight = data[j][WEIGHT];
//cout << "before temp_price " << temp_price << " temp_weight " << temp_weight << endl;
data[j][PRICE] = compare_p;
data[j][WEIGHT] = compare_w;
//cout << "before data[j][PRICE] " << data[j][PRICE] << " data[j][WEIGHT] " << data[j][WEIGHT] << endl;
compare_p = temp_price;
compare_w = temp_weight;
//cout << "data[j][PRICE] = " << data[j][PRICE] << endl;
}
else if(data[j][PRICE] > compare_p){
continue;
}
if(temp_price == 0) break;
}
}
int remain_Kg = W;
for(int k=0 ; k < N ; k++){
//cout << "remain_KG = " << remain_Kg << endl;
//cout << "data[k][WEIGHT] = " << data[k][WEIGHT] << endl;
//cout << "remain_Kg - data[k][WEIGHT] = " << remain_Kg - data[k][WEIGHT] << endl ;
if((remain_Kg - data[k][WEIGHT]) >= 0){
//cout << "data[k][PRICE] = " << data[k][PRICE] << endl;
result += (data[k][PRICE] * data[k][WEIGHT]);
//cout << "result = " << result << endl;
remain_Kg -= data[k][WEIGHT];
} else {
result = result + (remain_Kg * data[k][PRICE]);
//cout << "result = " << result << endl;
//cout << (unsigned)result;
break;
}
}
cout << result;
return 0;
}
결과 : 테스트 예제 통과 / 테스트 실패 (timeout)
알고리즘 재 정리
timeout case 가 있어서 더 빠르게 계산할 수 있게 리팩토링이 필요하다.
현재 코드는 가격이 큰것부터 작은 것 순으로 정렬을 하고 O(NlgN), W 만큼 N개를 넣는 O(N+P) 시간 복잡도를 가지고 있다. O(N+P) 는 거의 O(N)과 같고, 정렬의 시간 복잡도가 높다. 이 정렬을 O(N) 으로 변경해야 하는데,
가격의 최대는 10,000 이기에 가격은 배열의 index로 쓰고 무게는 배열의 값으로 쓰면,
그리고 가격이 동일한 것은 무게를 합쳐서 동일한 index에 넣으면 높은 index(가격)부터 최대 N번만 계산하면 된다.
코드
결과 : 테스트 예제 통과 / 테스트 통과
이번 알고리즘은
시간 복잡도를 개선하여 좀더 효율적인 코드를 작성하는 리팩토링 할 수 있어서 좋았다.