글 읽기 - 30 질문있어요!

testtest4 4년 전 0

저는 이걸 순열이라고 생각하고 큰 수대로 정렬시킨 뒤에

30으로 나눌 수 있는 가장 큰수를 출력하게끔 했거든요 만약 아니면 순열을 바꾸어서 그다음 수를 계산하고.. 이런 식입니다.

보니까 입력받은 숫자를 전부 더한 뒤 3으로 나누는 알고리즘이 있던데

제 알고리즘이랑 별다른 차이가 없는 것 같은데 왜 저는 틀리게 나오는지 이해가 가지 않습니다.

테스트 케이스나 반례를 여럿 해봤지만 다른 케이스는 모르겠네요

bool zeroFlag = false;

bool desc(char a, char b) {
	if (a == '0' || b == '0') zeroFlag = true;
	return a > b;
}

int main() {
	string srr;

	cin >> srr;

	sort(srr.begin(), srr.end(), desc);

	bool flag = false;
	long long int Sum;

	if (!zeroFlag) {//false 0이 아무것도 없을경우 
		cout << -1;
	}
	else {
		do {
			Sum = 0;
			for (int i = srr.size() - 1; i >= 0; i--) {
				Sum += (srr[i]-'0') * pow(10, srr.size() - 1 - i);
			}
			//cout << Sum <<'\n';
			if (Sum % 30 == 0) {
				flag = true; 
				cout << Sum;
				break;
			}
		} while (next_permutation(srr.begin(), srr.end()));

		if (!flag) cout << -1;
	}
}

nahwasa 4년 전 1

맞으셨군요! 해결하신듯하니 정답과는 별개로,

일단 next_permutation은 쓰실 필요가 없습니다.

10의 배수 -> 끝자리가 0

3의 배수 -> 각 자리의 합이 3의 배수

즉 0이 포함안되면 30의 배수는 무조건 아닌거고,

0을 제외한 나머지의 합이 3의 배수가 아니라면 애초에 30의 배수가 아닙니다.

testtest4 4년 전 1

음 그렇군요 말씀하신대로 문제를 풀었는데 정답이 나오긴 했습니다!

그런데 궁금한 게 왜 순열로 해서 풀면 틀릴까요? 별다른 차이를 느끼지 못하겠습니다..

결국 그리디 알고리즘으로 생각해보면 가장 큰 수에서 조금씩 줄여나가는 거라고 생각해서 30으로 나뉘기만 하면 30의 배수가 아닌가요?

nahwasa 4년 전 1

http://www.cplusplus.com/reference/algorithm/next_permutation/?kw=next_permutation

글쌔요 이전과 맞은 코드가 어떻게 다른진 모르겠지만,

next_permutation 리턴값 보시면,

그저 start부터 end까지 인접한 두 값을 비교하는식으로 짜여져 있습니다.

즉 최종적으로 false가 뜰때는 다음 순열이 없을때가아니고,

5,4,3,2,1,0 여기까지 도달하면 false일듯하네요.

저도 c++에 좀 약하긴 해서 확답을 못드리겠는데 제가 생각할때는

애초에 정렬을 마치셨으니 아마 next_permutation은 계속 false여서 어차피 동작을 안했을것 같습니다.

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

문제

문제

출처

ICPC

30 질문있어요!

testtest4 4년 전 0

nahwasa 4년 전 1

testtest4 4년 전 1

nahwasa 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말