백준 12865 평범한 배낭 C++/DP/냅색 알고리즘/골드5

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

아이디어

예전에 알고리즘 공부하면서 풀어본 유형이구

그 기억을 더듬어 다시 풀었다.

 

그런데 그때 푼대로 풀었는데 백준에서는 계속 틀렸다고 빡구먹었다. 

왜지 ..!!!!

우선 그때 배웠던 방법대로 푼 것은

 

int main() {
    FILE* p_file = NULL;
    freopen_s(&p_file,"input.txt", "rt", stdin);
    
    ios_base::sync_with_stdio(false);

    int n, m, w, v,i,j;

    // 무게와 한게값
    cin >> n >> m;
    vector<int> dy(m + 1, 0);

    for ( i = 0; i < n; i++) {
        cin >> w >> v;

        for (j = w; j <= m; j++) {
            // 기존값과 w라는 무게를 담는 경우의 무게
            // 기존값이 크면 기존값 쓰고 무게를 담는 경우 가치가 더 크면 새값을 적용한다.
            dy[j] = max(dy[j],dy[j-w] + v);
        }

    }
    cout << dy[m];
    return 0;
}

 

 

하도 안풀려서 구글링한 방법으로 다시 푼 방법

int main()
{
	ios_base::sync_with_stdio(false);

	cin >> N >> K;

	for (int i = 1; i <= N; i++)
		cin >> W[i] >> V[i];

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= K; j++)
		{

			// 만약 j - w[i] 가 0보다 크거나 같으면 	
            // 즉 해당 값을 넣을 수 있는 무게라면
            // 직전의 값과 새로 넣은 값 중 큰 가치값을 넣는다.
			if (j - W[i] >= 0) DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);
            
            // 만약 가치가 더 크지 않다면 직전의 값을 넣는다.
			else DP[i][j] = DP[i - 1][j];
		}
	}

	cout << DP[N][K];

}

 

둘 차이점은 벡터대신 배열 사용

값을 받으면 즉시 계산 / 받고나서 한번에 계산

아직도 저 위의 방법이 왜 백준에서는 안먹히는지 몰겠다.

 

아시는분 계시면 댓글 달아주시면 감사하겠숩ㅣㄴ다.