글 읽기 - 반례좀 찾아주시면 정말 감사하겠습니다.

phc91 3년 전 0

정말 모르겠습니다. 고수님들 도와주시면 정말 감사하겠습니다.ㅠㅠㅠ

감사합니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N;
vector<int> W; //추의 무게
int M; 
vector<int> marble;
vector<bool> dp;
int sum = 0;
void Input() {
	cin >> N; W.assign(N, 0);
	for(int i=0;i<N;i++) { cin >> W[i]; sum += W[i]; }
	cin >> M; marble.assign(M, 0);
	for(int i=0;i<M;i++) cin >> marble[i];
	dp.assign(sum+1, 0);
}

int main() {
	Input();
	dp[W[0]] = true;
	int s = W[0];
	for(int i=1;i<N;i++) {
		dp[W[i]] = true; // i와 동일한 무게의 구슬은 무조건 알 수 있다. 
        // s : 0번째 추의 무게 + 1번째 추의 무게 + ... + i-1번째 추의 무게
		for(int j=0;j<=s;j++) {
			if (dp[j]) { //i-1번째에서 알아낼 수 있는 구슬이였다면 dp[j]가 true라 생각 
				dp[abs(W[i] - j)] = true;
				dp[W[i] + j] = true;
			}
		}
		s += W[i];
	}
	for(int i =0;i<M;i++) {
		if (marble[i] > s) cout << "N ";
		else {
			char c = dp[marble[i]] ? 'Y' : 'N';
			cout << c << " ";
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

반례좀 찾아주시면 정말 감사하겠습니다.

phc91 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말