글 읽기 - 반례 부탁드립니다!

skesswswkk 4년 전 1

주어진 입/출력과 질문의 반례에서는 모두 정답을 출력합니다. 아래 코드에 대한 반례 부탁드립니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int alpha[26 + 1];

bool cmp(int a, int b) {
	if (a > b) {
		return true;
	}
	else {
		return false;
	}
}

int main() {
	int n;
	cin >> n;

	while (n--) {
		string s;
		cin >> s;

		int size = s.size();
		for (int i = 0; i < size; ++i) {
			alpha[s[i] - 65] += pow(10, size - i - 1);
		}
		sort(alpha, alpha + 26, cmp);
	}

	int sum = 0;
	int nine = 9;
	for (int i = 0; i < 26; ++i) {
		if (alpha[i] == 0) {
			cout << sum << endl;
			return 0;
		}
		else {
			sum += alpha[i] * nine;
			nine--;
		}
	}
}

201812106 4년 전 2

반례입니다

skesswswkk 4년 전 0

는 정답이 맞게 출력되는데

Z의 경우에만 9 + 8 = 17이 출력되는 이유를 알 수 있을까요?

201812106 4년 전 1

sort를 while문 안에서 하고 있기 때문입니다.

201812106 4년 전 0

A는 0번 alpha이므로, 배열에 1 0 0 0 0 0 0 0 0 0 이므로 내림차순으로 정렬을 해도 문제가 없습니다.

하지만 Z는 25번이므로 정렬을 하면 0 0 0 0.... 1 -> 1 0 0 0 0 0 0 .. 이 되고

다시 한번 더 Z가 들어왔으니 1 0 0 0 0 0.... 1이 돼 버립니다.

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

문제

문제

출처

ICPC

반례 부탁드립니다!

skesswswkk 4년 전 1

201812106 4년 전 2

skesswswkk 4년 전 0

201812106 4년 전 1

201812106 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말