백준 3052번: 나머지

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

3052번: 나머지

 

 

0. 알고리즘 분류

 1차원 배열

 

 

1. 문제

 

 두 자연수 A와 B가 있을 때, A%B는 A를 B로 나눈 나머지 이다. 예를 들어, 7, 14, 27, 38을 3으로 나눈 나머지는 1, 2, 0, 2이다. 수 10개를 입력받은 뒤, 이를 42로 나눈 나머지를 구한다. 그 다음 서로 다른 값이 몇 개 있는지 출력하는 프로그램을 작성하시오.

 

 

2. 풀이

 

 문제를 처음 봤을 때 상당히 쉬울 거라 생각했지만, 생각보다 간단하게 풀리지는 않았다. 10개의 자연수를 42로 나눈 나머지를 구하여, 서로 다른 값이 몇 개 있는지를 찾아라.. 머리가 아팠던 부분은 "서로 다른 값의 갯수" 였다. 단순무식하게 for문 2번 겹쳐 완전탐색으로 찾는 방법이 있었지만 그렇게 풀고 싶지는 않았다.

 

 내가 선택한 방법은 배열 2개를 이용한 방법이다. 10개의 나머지를 저장하는 배열과 0부터 41까지의 값의 존재유무를 확인하는 배열이다. 결과적으로 for문 2개를 겹쳐 사용해서 시간복잡도 측면에선, 처음 생각했던 방법과 다를 게 없다. 어려운 방법은 아니므로, 따로 주석이나 풀이는 적지 않는다.

 

 

3. 코드

#include <iostream>

using namespace std;

int main(void) {
	int p = 42;
	int n = 10;
	int numbers[n];
	
	int memory[p];
	for (int i = 0; i < p; i++)
		memory[i] = false;
		
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
		a[i] = numbers[i] % p;
		if (memory[numbers[i]] == false)
			memory[numbers[i]] = true;
	}
	
	int num = 0;
	for (int i = 0; i < p; i++)
		if (memory[i] == true)
			num++;
	
	cout << num;
	return 0;
}