글 읽기 - 1715번 반례나 오류좀 부탁드립니다.

cksgml2237 3년 전 2

답은 잘 나오지만 올리면 틀린다고 나오네요.

혹여 반례나 오류가 보이거나 제가 문제를 잘못 이해했다면 도움 부탁드립니다.

정렬 이후 전의 결과를 box 변수에 저장 cnt 변수에 box 변수의 값과 이번의 카드 수를 누적합니다.

10 20 30 40 -> (10+20)+(30+30)+(60+40)=190

#include<iostream>
#include<array>
#include<algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, box;
	long long cnt = 0;
	array <int, 100000> card;

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> card[i];

	sort(card.begin(), card.begin() + n);

	for (int i = 0; i < n; i++)
		cout << card[i] << endl;
	box = card[0];
	for (int i = 1; i < n; i++) {
		cnt += box + card[i];
		box = box + card[i];
	}
	cout << cnt;

	return 0;
}

adfsfsf 3년 전 1

23~24는 디버깅을 위해 적으신 줄 같네요. 주석처리 해보셨나요?

adfsfsf 3년 전 1

그리고 순차적으로 더하는 것보다 더 나은 경우는 많습니다. 합칠 때는 합치는 시점 기준으로 가장 적은 2개의 뭉치를 합쳐야 합니다.

cksgml2237 3년 전 1

답변 달아주셔서 감사합니다.

23~24는 말씀하신 대로 오류가 있을지 확인하면서 들어간 과정이고 답변을 제출하면서는 없앴었습니다.

저는 두 번째로 댓글 달아주신

'합칠 때는 합치는 시점 기준으로 가장 적은 2개의 뭉치를 합쳐야 합니다.'

이 말씀의 의미가 흥미로운데요.

저로서는 완벽한 이해가 힘든 것 같습니다.

저는 정렬로써 가장 적은 카드 수를 합치는 과정이 해결됐다고 생각되는데요.

저의 이해력이 부족한 것 같습니다. ㅠㅠ

조금 더 부연 설명을 보태주셨으면 합니다.

죄송합니다. ㅠㅠ

답변 제출은 아래와 같이 했습니다!

#include<iostream>
#include<array>
#include<algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, box;
	long long cnt = 0;
	array <int, 100000> card;

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> card[i];

	sort(card.begin(), card.begin() + n);

	box = card[0];
	for (int i = 1; i < n; i++) {
		cnt += box + card[i];
		box = box + card[i];
	}
	cout << cnt;

	return 0;
}

adfsfsf 3년 전 9

아래와 같은 예시가 있다고 합시다. 작성하신 코드를 기준으로 먼저 해볼게요.

정렬은 되어 있으므로 스킵합니다.

1번 루프를 돕니다. box 초기값이 5, card[1]은 6입니다. 합은 11입니다. box와 cnt가 11이 됩니다.

2번째 루프를 돕니다. card[2]는 7이네요. box가 11이므로 다음 box는 18, cnt는 29가 됩니다.

3번째입니다. card[3]은 8입니다. box가 18이므로 다음 box는 26, cnt는 55가 되겠네요.

따라서 출력은 55가 나옵니다.

하지만 답은 55가 아닙니다.

아래의 순서가 정답을 구하는 순서입니다.

1. 가장 작은 값인 5와 6을 더합니다. 그러면 11이군요. cnt도 11이 됩니다. 5와 6을 카드 뭉치 목록에서 빼고 11을 추가합니다. 현재 남은 뭉치는 7, 8, 11입니다.

2. 가장 작은 7과 8을 더합니다. 15가 됩니다. cnt는 11+15인 26이 됩니다. 현재 카드 뭉치는 11, 15입니다.

3. 마지막으로 남은 뭉치 2개를 더합니다. 26이군요. cnt는 26+26인 52입니다.

이런 식으로, 합친 후 존재하는 뭉치 목록을 갱신하는 것을 반복해야 합니다. 연결 리스트 방식이나 버킷과 결합한 연결리스트를 추천할게요.

cksgml2237 3년 전 0

감사합니다! 덕분에 제 풀이가 틀렸다는 걸 알고 조언 주신 대로 list에 대해 공부하는 시간을 가져봤습니다.

list를 처음 다루는지라 중간에 오류도 많이 나고 고민도 많이 해보았습니다.

아래의 결과가 나왔는데 웹서핑을 통해 독학으로 배우 다보니 다루는 방식이 많이 서툴렀기도 하고

목록을 갱신하는 과정에서 많이 조잡했는지 시간 초과가 나오네요. ㅠ

버킷 정렬과 list의 결합을 더 공부해서 아래에 녹여내보겠습니다.

#include<iostream>
#include<list>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, box;
	long long cnt = 0;
	list<int> card;
	list<int>::iterator liter;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> box;
		card.push_back(box);
	}
	card.sort();

	while (1) {
		if (card.size() == 2) { // 2개 남았을 경우 그냥 더해주고 끝냄
			cnt += card.front();
			card.pop_front();
			cnt += card.front();
			break;
		}
		box = card.front();
		card.pop_front();
		cnt += box + card.front();
		box += card.front();
		card.pop_front();
		if (box > card.back()) // 맨 뒷값보다 클 경우 그냥 맨 뒤에 넣는다.
			card.push_back(box);
		else {
			for (liter = card.begin(); liter != card.end(); ++liter) { // 박스의 자리를 찾는다.
				if (box <= *liter) {
					card.insert(liter, box);
					break;
				}
			}
		}
	}

	cout << cnt;

	return 0;
}

choko100 3년 전 1

질문과 댓글 모두 감사드립니다. 덕분에 저도 제 코드의 문제를 금방 발견할 수 있었습니다.

adfsfsf 1년 전 1

nicolao00 님

저는 답이 26이라고 하지 않았습니다. 3번을 다시 보시면 cnt가 52라고 잘 적어놨습니다.

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

문제

문제

출처

ICPC

1715번 반례나 오류좀 부탁드립니다.

cksgml2237 3년 전 2

adfsfsf 3년 전 1

adfsfsf 3년 전 1

cksgml2237 3년 전 1

adfsfsf 3년 전 9

cksgml2237 3년 전 0

choko100 3년 전 1

adfsfsf 1년 전 1

nicolao00 님

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말