글 읽기 - 맞왜틀 입니다..

simm4256 4년 전 0

각 수마다 (이전 수들로 만들 수 있는 수 + 이번 수 % n) 을 0 ~ n-1까지 체크했습니다.

간단하다고 생각했는데 '틀'의 이유를 못찾겠습니다.

추가로 주어진 수 중 0이 있으면 답으로 0만 출력해도 되는건가요?

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int n, m, x, a[1010];
vector<int> v[510];

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	m = 2 * n - 1;
	int i, j;
	for (i = 0; i < m; i++)
		cin >> a[i];
	for (i = 0; i < m; i++) {
		x = a[i];
		if (!x) {
			cout << '0';
			return 0;
		}
		bool isFirst = false;
		if (v[x].empty()) {
			v[x].push_back(x);
			isFirst = true;
		}
		for (j = 1; j < n; j++) {
			if (v[j].empty() || (j == x && isFirst) || !v[(j + x) % n].empty()) 
				continue;
			// 이전 수들로 j를 만들 수 있을 때 j+x%n도 만들 수 있다.
			v[(j + x) % n] = v[j];
			v[(j + x) % n].push_back(x);
			if ((j + x) % n == 0) {
				for (auto it : v[(j + x) % n])
					cout << it << ' ';
				return 0;
			}
		}
	}
	cout << -1;
}

snrnsidy 4년 전 1

1 1 3 3 0 2 2 반례입니다.

simm4256 4년 전 0

감사합니다.

simm4256 4년 전 0

check 배열로 해당 반례는 해결했는데 여전히 틀 받네요 ㅠㅠ

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

int n, m, x, a[1010];
vector<int> v[510];

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	m = 2 * n - 1;
	int i, j;
	for (i = 0; i < m; i++)
		cin >> a[i];
	for (i = 0; i < m; i++) {
		x = a[i];
		if (!x) {
			cout << '0';
			return 0;
		}
		bool isFirst = false, check[510] = { false, };
		if (v[x].empty()) {
			v[x].push_back(x);
			isFirst = true;
		}
		for (j = 1; j < n; j++) {
			if (v[j].empty() || (j == x && isFirst) || !v[(j + x) % n].empty() || check[j])
				continue;
			// 이전 수들로 j를 만들 수 있을 때 j+x%n도 만들 수 있다.
			v[(j + x) % n] = v[j];
			v[(j + x) % n].push_back(x);
			check[(j + x) % n] = true;
			if ((j + x) % n == 0) {
				for (auto it : v[(j + x) % n])
					cout << it << ' ';
				return 0;
			}
		}
	}
	cout << -1;
}

snrnsidy 4년 전 0

2
0 1 1 반례입니다

simm4256 4년 전 0

0 입력을 어떻게 처리하는 지 몰라서 아예 무시하고도 제출해봤습니다.

아래 코드론 1 1 나옵니다만 여전히 틀 입니다 ㅠ

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int n, m, x, a[1010];
vector<int> v[510];

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	m = 2 * n - 1;
	int i, j;
	for (i = 0; i < m; i++)
		cin >> a[i];
	for (i = 0; i < m; i++) {
		x = a[i];
		if (!x)
			continue;
		bool isFirst = false, check[510] = { false, };
		if (v[x].empty()) {
			v[x].push_back(x);
			isFirst = true;
		}
		for (j = 1; j < n; j++) {
			if (v[j].empty() || (j == x && isFirst) || !v[(j + x) % n].empty() || check[j])
				continue;
			// 이전 수들로 j를 만들 수 있을 때 j+x%n도 만들 수 있다.
			v[(j + x) % n] = v[j];
			v[(j + x) % n].push_back(x);
			check[(j + x) % n] = true;
			if ((j + x) % n == 0) {
				for (auto it : v[(j + x) % n])
					cout << it << ' ';
				return 0;
			}
		}
	}
	cout << -1;
}

snrnsidy 4년 전 1

주어진 수가 0이 하나라도 있다고 해서 0으로 출력하면 안됩니다. 그리고 코드를 읽어보면 무조건 0이 될 때 이때까지 만들어진 수들을 다 출력시키고 종료시키는 거 같은데 n개를 뽑아서 만들었는지에 대한 검사가 없어보이네요......

simm4256 4년 전 0

20 line에서 continue로 처리했습니다. 0 입력은 답과 무관하기 때문에 그냥 패스한겁니다.

simm4256 4년 전 0

아 이제보니 제가 완전히 문제를 잘못 이해하고 있었네요.. 답의 개수가 N개가 되어야 했었네요. 감사합니다.

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

문제

문제

출처

ICPC

맞왜틀 입니다..

simm4256 4년 전 0

snrnsidy 4년 전 1

simm4256 4년 전 0

simm4256 4년 전 0

snrnsidy 4년 전 0

simm4256 4년 전 0

snrnsidy 4년 전 1

simm4256 4년 전 0

simm4256 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말