[C++] 3052 나머지

 

https://www.acmicpc.net/problem/3052

3052번: 나머지

 

 

 

풀이 ( C++)

---

#include <iostream>
#include <string>

using namespace std;
int main()
{

	int data[100];
	bool array[100] = { 0, };

	for (int i = 0; i < 10; i++)
	{
		cin >> data[i];
		data[i] = data[i] % 42;
	}
	
	
	for (int j = 0; j < 10; j++)
	{

		for (int i = 0; i < 42; i++)
		{
			if (data[j] == i)
			{
				array[i] = 1;
			}
		}
	}
		
	int count = 0;

	for (int i = 0; i < 42; i++)
	{
		

		if (array[i] == 1)
			count++;
	}
	
	cout << count << endl;
}

 

알고리즘

 

어렵지 않게 풀 수 있는 문제였습니다.

 

물론 저는 조금 더 복잡하고 향상되지 않은 풀이 방식입니다. 그래도 제가 접근한 방식도 어떤 분한테는 도움이 될 수 있을까 해서 이렇게 적어놓습니다.

 

먼저 이 문제를 풀기에 생각해야 하는 것은 바로 BOOL 함수입니다. 서로 다른 나머지의 수가 무엇인지는 상관없고 그 나머지의 개수를 구해야 하기 때문입니다. 

 

1. 배열 정의

int data[100];
bool array[100] = { 0, };

따라서 저는 나머지를 찾을 배열에 이렇게 0으로 초기화를 해주었습니다. 만약 나머지가 나온다면 이 배열의 칸이 1로 바뀔 것입니다. 

 

2. int i 값 넣어준 다음 나머지 저장

	for (int i = 0; i < 10; i++)
	{
		cin >> data[i];
		data[i] = data[i] % 42;
	}

값 10개를 입력받은 후 바로 나머지를 구해주는 식을 해줍니다. data[i % 42]++ 이런식으로 해주셔도 상관없습니다.

 

3. 나머지가 있는 곳에 배열을 1로 바꿔주기

	for (int j = 0; j < 10; j++)
	{

		for (int i = 0; i < 42; i++)
		{
			if (data[j] == i)
			{
				array[i] = 1;
			}
		}
	}

나머지는 총 0부터 41까지가 나옵니다. 따라서 나머지인 배열을 array라고 두고 만약 나머지가 나오는 곳이 있다면 그곳을 0 말고 1을 덮어줄 것입니다. 이렇게 이중 for문을 사용해서 만들어주었습니다.

 

4. count를 통해 나머지의 개수 세주기

	int count = 0;

	for (int i = 0; i < 42; i++)
	{
		

		if (array[i] == 1)
			count++;
	}

int count를 맨 위에 배열과 같이 선언해줘도 되지만 저는 풀면서 생각을 하느라 여기서 적었습니다. count++로 array[i] == 1일 때를 세주었습니다. 

 

이후 count를 출력하면서 식은 마무리 됩니다. 

 

다른 풀이

---

#include <iostream>
using namespace std;

int main() {
	int num;
	int rm[42] = { 0 };
	int count = 0;

	for (int i = 0; i < 10; i++) {
		cin >> num;
		rm[num % 42]++;
	}

	for (int i = 0; i < 42; i++) {
		if (rm[i] != 0)
			count++;
	}
	cout << count << endl;
}

이 식은 더 간단히 그리고 빠르게 처리할 수 있습니다.

 

바로 for문을 통해서 cin>>num을 입력받을 때 곧바로 나머지를 구한 후 그 나머지를 array에 넣어주는 것입니다. 이 때 array는 0으로 초기화 되어있기 때문에 0이 아닌 값이 나온 것은 나머지가 있는 것이며 이것을 for문을 통해 검증해주면 되는 것입니다.