백준 2294 동전2, c++

 

 

 

처음 작성한 코드는 다음과 같다.

(+ 이 문제에서는 최소 경우를 구해주어야 하므로 비교해서 작은 경우를 사용하는 것이 중요했다.)

하지만 시간초과 오류가 났다.

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    
    vector<int> arr(n);
    vector<int> dp(k+1);
    
    for(int i=0; i<n; i++)
        cin >> arr[i];
    
    dp[0] = 1;
    int min = 101;
    int temp;
    for(int i=0; i<n; i++){
        for(int j=arr[i]; j<=k; k++){
            temp = dp[j] + dp[j-arr[i]];
            if(temp < dp[j])
                dp[j] = temp;
        }
    }
    
    if(dp[k] == 1)
        cout << "-1";
    else
        cout << dp[k]];
    
    return 0;
}

 

 

 

시간초과 오류는 j++이 아니라 k++이라고 해서 났던 간단한 오류였다.

하지만 코드를 맞게 고쳐도 계속 틀렸다고 나왔다.

구글링을 통해 다른 코드와 비교했을 때, 고친 후의 내 코드와 크게 다른 점은 못느껴서 처음에는 어디서 오류가 나는 것인지는 찾아내지 못했다.

하지만 min한 값을 비교해 저장하는 과정에서 여기서는 기존dp[]값에 더해주는 게 아니라, 기존 dp값과 비교해서 더 큰 값을 dp에 저장해야 하는 것이므로 dp[j] + dp[j-arr[i]]형태가 아닌 그냥 dp[j-arr[i]]만 temp에 넣어주면 되는 부분이 문제였다.

앞으로는 사소한 논리도 다시 생각해보아야겠다.