-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
dp를 이차원 배열로 만들어서 풀어봤는데, 틀립니다.
24.05.20 18:16 작성 조회수 64
0
http://boj.kr/7c9fc1fdb4894c518c897537de03f02b
선생님, 안녕하세요~
dp를 이차원 배열로 만들어서 n번째 인덱스까지 돈m을 썼을때의 최대 칼로리 양을 저장하게 했습니다.
int dp[5004][10004]; // n번째 인덱스까지 돈m을 썼을때 최대 칼로리양그 후 나머지 부분은, 동전문제에서 했던 것과 비슷하게,
단지 이차원 배열이니깐 dp[i][j]를 비교할 때, 가격이 이전 인덱스가 더 큰지, 아니면 이번 인덱스에서 가격만큼을 빼고 칼로리만큼을 더한게 더 큰지 비교해주도록 했는데요.
for (int i = 1; i <= n; i++)
{
for (int j = 1 * 100; j <= m * 100; j++)
{
if (price[i] > j)
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - price[i]] + cal[i]);
}
mx = max(mx, dp[i][j]);
}
}지금 제가 생각하기에, 코드를 이렇게 짰을때, 일차원배열과 이차원배열이 큰 차이가 있나 싶기도하고, 다른 냅색문제에서 이렇게해서 통과하는 경우가 있었기에,
어떤 차이가 있을까, 반례가 뭐가있을까 질문드리고 싶습니다.
답변을 작성해보세요.
1
큰돌
지식공유자2024.05.22
안녕하세요 google님 ㅎㅎ
dp를 이차원 배열로 만들어서 n번째 인덱스까지 돈m을 썼을때의 최대 칼로리 양을 저장하게 했습니다.
>>
무슨 코드인지 이해했습니다. 괜찮은 로직입니다. ㅎㅎ
#include <bits/stdc++.h>
using namespace std;
int n, c;
double m, p;
int dp[5004][10004];
int cal[5004];
int price[5004];
int m1, m2;
int main() {
while (true) {
scanf("%d %d.%d", &n, &m1, &m2);
int max_price = m1 * 100 + m2;
if (n == 0) {
break;
}
for (int i = 1; i <= n; i++) {
scanf("%d %d.%d", &c, &m1, &m2);
cal[i] = c;
price[i] = m1 * 100 + m2;
}
int mx = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= max_price; j++) {
if (price[i] > j)
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - price[i]] + cal[i]);
}
mx = max(mx, dp[i][j]);
}
}
printf("%d\n", mx);
}
return 0;
}
다만 이렇게 해야 되지 않을까요?
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
답변 1