if (dy[j][0] < dy[j - k][0] + arr[k][i]) {
dy[j][0] = dy[j - k][0] + arr[k][i];
for (int t = 1; t <= m; t++) {
if (t == i) dy[j][i] = k;
else dy[j][t] = dy[j - k][t];
}
}
3. 문제풀이 코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, m, arr[301][21], dy[301][21];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int tmp;
cin >> tmp;
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
for (int i = 1; i <= m; i++) {
for (int j = n; j >= 0; j--) {
for (int k = 0; k <= j; k++) {
//k는 가격
if (dy[j][0] < dy[j - k][0] + arr[k][i]) {
dy[j][0] = dy[j - k][0] + arr[k][i];
for (int t = 1; t <= m; t++) {
if (t == i) dy[j][i] = k;
else dy[j][t] = dy[j - k][t];
}
}
}
}
}
cout << dy[n][0] << '\n';
for (int i = 1; i <= m; i++) {
cout << dy[n][i] << ' ';
}
}
그러면 메모리의 범위가 1 ≤ M ≤ 10,000,000 이어서 배열의 최대 사이즈를 넘어 사용할 수가 없다.
그런데 알고보니 메모리를 기준점으로 하는 게 아니라
비용을 기준점으로 하면 비용의 최댓값이 100이고 n의 최댓값이 100이어서
배열을 dy[10001]로 잡아주면 충분하다.
dy[i] 는 cost가 i 일 때 최대 확보한 메모리이다.
점화식
dy[j] = max(dy[j], dy[j - cost[i]] + mem[i]);
문제처럼 입력이 다음과 같을 때
5 60
30 10 20 35 40
3 0 3 5 4
dy 테이블은
mem|cost
0
1
2
3
4
5
6
...
10000
30 | 3
0
0
0
30
30
30
30
30
30
10 | 0
10
10
10
10
40
40
40
40
40
20 | 3
10
10
10
40
40
40
60
60
75
35 | 5
10
10
10
40
40
45
60
60
75
40 | 4
10
10
10
40
50
50
60
80
100
각 문제를 적용했을 때 확보된 메모리가 60이상인 최소의 비용은
6이다.
문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, m, mem[101], cost[101], dy[10001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> mem[i];
}
for (int i = 0; i < n; i++) {
cin >> cost[i];
}
for (int i = 0; i < n; i++) {
for (int j = 10000; j >= cost[i]; j--) {
dy[j] = max(dy[j], dy[j - cost[i]] + mem[i]);
}
}
for (int i = 0; i <= 10000; i++) {
if (dy[i] >= m) {
cout << i;
break;
}
}
}
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dy[101][1020];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=1; i<=n ;i++){
int point, time;
cin >> point >> time;
for(int j = time; j<=m; j++){
dy[i][j] = max(dy[i-1][j-time] + point, dy[i-1][j]);
}
}
cout << dy[m];
}
1차원
for문을 뒤에서부터 돌면 해결된다
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dy[1020];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=1; i<=n ;i++){
int point, time;
cin >> point >> time;
for(int j = m; j>=time; j--){
dy[j] = max(dy[j-time] + point, dy[j]);
}
}
cout << dy[m];
}
비주얼스튜디오 : no appropriate default constructor available,
dev C++ : no matching function for call to 'Block::Block()'
[Error] no matching function for call to
알고리즘 문제를 풀다가 다음과 같은 에러를 발견했습니다.
본 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
struct Block{
int area;
int height;
int weight;
Block(int a, int b, int c){
area = a;
height = b;
weight = c;
}
bool operator<(const Block &b) const{
return(area > b.area);
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<Block> v(n+1);
vector<int> ch(n+1);
v[0] = Block(INT_MAX, 0 , INT_MAX);
for(int i=1; i<=n; i++){
int a, b, c;
cin >> a >> b >> c;
v[i] = Block(a,b,c);
}
sort(v.begin(), v.end());
ch[0] = 0;
for(int i=1; i<=n; i++){
int max_height = 0;
for(int j=i-1; j>=0; j--){
if(v[i].area < v[j].area && v[i].weight < v[j].weight){
max_height = max(max_height, ch[j]);
}
}
ch[i] = max_height + v[i].height;
}
int ans =0;
for(int i=1; i<=n; i++){
ans = max(ans, ch[i]);
}
cout << ans;
}
여기서 에러가 발생한 부분은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
struct Block{
int area;
int height;
int weight;
Block(int a, int b, int c){
area = a;
height = b;
weight = c;
}
bool operator<(const Block &b) const{
return(area > b.area);
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
//이 부분
vector<Block> v(n+1);
}
Block 이라는 구조체를 만들고
Block 자료형으로 이루어진 벡터를 만들어
벡터 사이즈를 n+1로 동적으로 초기화해주었는데 오류가 발생했습니다.
그래서 다음 코드와 같이
벡터 사이즈를 초기화하지 않고 다시 코드를 짜니 오류가 발생하지 않았습니다.
#include <bits/stdc++.h>
using namespace std;
struct Block{
int area;
int height;
int weight;
Block(int a, int b, int c){
area = a;
height = b;
weight = c;
}
bool operator<(const Block &b) const{
return(area > b.area);
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<Block> v;
}
(예: 배열의 요소로) 클래스를 만들 수 있도록 허용 하려면 기본 생성자도 제공 해야 합니다.
기본 생성자는 모든 매개 변수에 기본값을 사용하는 생성자일 수 있습니다."
구조체, 클래스 내에 기본생성자를 구성하지 않고
벡터의 사이즈를 동적으로 초기화해주면 이런 오류가 발생할 수 있는 것 같습니다.
그래서 해결방법으로는
1. 사이즈를 동적으로 초기화 하지 않거나
2. 구조체나 클래스에 기본 생성자를 추가해주면 오류가 발생하지 않습니다.
1번은 위에서 push_back을 이용한 방법이고
2번은 다음 코드와 같이 해주면 됩니다.
#include <bits/stdc++.h>
using namespace std;
struct Block{
int area;
int height;
int weight;
// 기본 생성자 추가
Block(){
}
Block(int a, int b, int c){
area = a;
height = b;
weight = c;
}
bool operator<(const Block &b) const{
return(area > b.area);
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<Block> v(n+1);
}
