글 읽기 - 제 코드의 문제점을 알고 싶습니다. / 1차원 배열로는 풀 수 없나요?

iomanip0107 1년 전 0

아래와 같이 풀이하였는데 계속 틀립니다. 2시간 넘게 쳐다보고 있는데요..

게시판의 반례를 다 넣어보고 모두 통과시키려 하다 보니 수정하면서 좀 억지로 끼워 맞춘 부분이 있기는 합니다.

덕분에 질문 게시판에 있는 반례는 모두 통과를 하는데요. 여전히 제출하면 틀립니다.

어느 부분이 틀렸는지 알고 싶습니다.

도와주세요,,ㅠㅠ

-------------------------------------------------------------------------------

자려고 누웠다가 3번째 if문이 잘못된 것 같다고 인지하고 ( 중복 사용 문제 ) 2차원 배열로 풀이해서 통과하였습니다.

아래처럼 1차원 배열로는 풀이 방법이 없는걸까요?

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int C, S, Max = 0;

	cin >> C;
	vector<int> Chu(C);
	for (int i = 0; i < C; i++)
	{
		cin >> Chu[i];
		Max += Chu[i];
	}
	
	vector<bool> Dp(Max + 1, false); // 모든 추로 만들수 있는 최대 무게로 배열 크기 설정
	Dp[0] = true;

	for (auto elem : Chu)
	{
		for (int i = Max; i >= 1; i--)
		{
            // 무게 i를 기존에 사용한 추와 새로 사용할 추로 만들 수 있는가
			if (i - elem >= 0) Dp[i] = Dp[i] || Dp[i - elem]; 
            // 새로 사용할 추를 저울에 두고 기존에 사용한 추를 반대편 저울에 두면 무게 i를 만들 수 있는가
			if (elem - i >= 0) Dp[i] = Dp[i] || Dp[elem - i]; 
            // (잘못된 부분?) 새로 사용할 추를 기존에 사용한 추 반대편 저울에 두면 무게 i를 만들 수 있는가
			if (elem + i <= Max) Dp[i] = Dp[i] || Dp[elem + i];
		}
	}

	cin >> S;
	for (int i = 0; i < S; i++)
	{
		int Sph;
		cin >> Sph;

		if (Sph <= Max && Dp[Sph]) cout << "Y ";
		else cout << "N ";
	}

	return 0;
}

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

문제

문제

출처

ICPC

제 코드의 문제점을 알고 싶습니다. / 1차원 배열로는 풀 수 없나요?

iomanip0107 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말