글 읽기 - 코드가 이상합니다

nill1024 3년 전 0

이 문제를 예전에 풀었었는데,

나중에 데이터 추가로 예외처리를 하러 들어왔다가 이상한 걸 발견했습니다.

이 문제를 풀 때의 DP는 여러가지가 있겠지만,저는 2차원 DP[i][j] = i까지의 애들을 골라서 비용 j로 가질 수 있는 최대 바이트

로 풀었거든요.

예외처리를 하다가 인터넷에 비슷한 코드가 있어 참고했는데, 그 코드는 이상하게도 29번째 줄에서 dp[i][j] 라고 되어있는데

이걸 dp[i][j]로 하던 dp[i-1][j] 로 하던 무조건 맞았습니다가 뜹니다.

왜 이런 현상이 일어나는지 알려주실 분 있나요?

#include <iostream>

using namespace std;
#define INF 987654321

int bytes[101];
int cost[101];
int dp[101][10001];

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N,M; cin >> N >> M;
    for(int i = 0; i < N; i++)
        cin >> bytes[i];
    for(int i = 0; i < N; i++)
        cin >> cost[i];

    int ans = INF;

    if(N == 1){
		cout << cost[0];
		return 0;
	}

    dp[0][cost[0]] = bytes[0];
    for(int i = 1; i < N; i++) {
        for(int j = 0; j <= 10000; j++) {
                if(j-cost[i] >= 0)
                    dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]]+bytes[i]);

                dp[i][j] = max(dp[i][j], dp[i-1][j]);

                if(dp[i][j] >= M) {
                    ans = min(ans, j);
                }
        }
    }
    cout<<ans;
    return 0;
}

ccc96360 3년 전 0

31번쨰 줄때문에 그런거 같은데요?

이거랑 같은 코드죠

if(j-cost[i] >= 0)
    dp[i][j] =  dp[i-1][j-cost[i]]+bytes[i]//dp[i][j] 의 초기값은 0이니..

dp[i][j] = max(dp[i][j], dp[i-1][j]);﻿

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코드가 이상합니다

nill1024 3년 전 0

ccc96360 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말