[백준 알고리즘] 3052번 : 나머지

문제

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

입력

첫째 줄부터 열번째 줄 까지 숫자가 한 줄에 하나씩 주어진다. 이 숫자는 1,000보다 작거나 같고, 음이 아닌 정수이다.

출력

첫째 줄에, 42로 나누었을 때, 서로 다른 나머지가 몇 개 있는지 출력한다.

예제 입력 1

39 40 41 42 43 44 82 83 84 85

예제 출력 1

6

힌트

39, 40, 41, 42, 43, 44, 82, 83, 84, 85를 42로 나눈 나머지는 39, 40, 41, 0, 1, 2, 40, 41, 0, 1이다. 서로 다른 값은 모두 6개가 있다.

 

내가 작성한 코드 (C++ 성공)

#include <iostream>

using namespace std;

int main(){

	int a;
	int b = 42;
	int rest[10] = {0};
	int sum = 0;
	
	for(int i=0; i<10; i++){
		cin >> a;
		rest[i] = a%b;
		for(int j=0; j<=i; j++){
			if(rest[i] == rest[j] && i != j){
				sum --;
				break;
			}
		}
		sum++;
	}
		
	cout << sum << "\n";
		
	return 0;
}

 

정리

이 문제를 간단하게 정리하면 42로 나눈 나머지가 중복을 제외하면 몇개가 있는지 알아내는 문제다.
간단한 문제인줄 알고 생각했다가 생각보다 오래 걸려서 해결했던 것 같다.
이 문제는 이렇게 생각해서 풀어나갔다.

1) 반복문으로 10개의 수를 입력받는다.
2) 입력받은 수를 42로 나누어 나머지를 구해서 배열에 넣는다.
3) 나머지를 배열에 넣은 후 반복문을 통해 이전의 나머지들과 비교한다.
4) 조건문을 통해 들어간 나머지의 값이 배열에 있는 나머지들의 값과 같은지 비교해서
    같다면 나머지의 갯수를 감소 , 다르다면 나머지의 갯수를 증가.
5) 나머지의 갯수를 출력한다.

이 문제의 핵심은 입력한 나머지의 값이 이전의 배열의 값들과 같은지 아닌지 비교해서 세어주는 것 같다.
이 부분에서 어떻게 갯수를 세어주어야할까? 에 대해서 생각을 많이 했던 것 같다.
지금 생각해보면 정말 간단한 문제인 것 같은데 잘못된 생각도 많았고 머릿 속에 윤곽이 잡히지 않았던 것같다.