[BOJ 백준] 30(10610) C++

 

링크 : https://www.acmicpc.net/problem/10610

10610번: 30

 

문제 설명 : 

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

 

입력 : 

첫째 줄에 정수 n(1 ≤ n ≤ 50,000)이 주어진다. 다음 n개의 줄에는 두 정수 y(0 ≤ |y| ≤ 1,000,000,000), r(1 ≤ r ≤ 1,000,000,000)이 주어지는데, 이는 y년도의 강수량이 r이라는 의미이다. 이러한 정보는 y가 증가하는 순서대로 주어진다. 그 다음 줄에는 정수 m(1 ≤ m ≤ 10,000)이 주어진다. 그 다음 m개의 줄에는 사람들의 이야기에 대한 정보를 나타내는 두 정수 Y, X(-1,000,000,000 ≤ Y < X ≤ 1,000,000,000)가 주어진다.

출력 : 

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

 

예제 입력 : 

80875542

예제 출력 : 

88755420

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 30 10610
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <algorithm>

#define MAX (100000+3)

using namespace std;

int N;
char inputStr[MAX];

// 내림차순 정렬
bool compare(const char& a, const char& b) {
	if (a > b) return true;
	return false;
}

bool isLastZero(int len);
bool isSumThreeBaeSoo(int len);

int main() {

	// 1. 입력
	//freopen("input.txt", "r", stdin);
	scanf("%s", inputStr);

	// 2. 문자열 정렬
	int len;
	for (len = 0; inputStr[len] != 0; len++);
	sort(inputStr, inputStr + len, compare);

	// 3. 마지막 문자열이 0이 아니면 불가
	if ( isLastZero(len)== true && isSumThreeBaeSoo(len)==true ) {
		printf("%s", inputStr);
	}
	else {
		printf("%d", -1);
	}
	return 0;
}

bool isLastZero(int len) {
	if (inputStr[len - 1] == '0') {
		return true;
	}
	return false;
}

bool isSumThreeBaeSoo(int len) {
	int result = 0;
	for (int i = 0; i < len; i++) {
		result += inputStr[i];
	}
	if (result % 3 == 0) {
		return true;
	}
	return false;
}
#endif