[BOJ] 3052번 - 나머지

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

3052번: 나머지

문제

두 자연수 A와 B가 있을 때, A%B는 A를 B로 나눈 나머지 이다. 예를 들어, 7, 14, 27, 38을 3으로 나눈 나머지는 1, 2, 0, 2이다. 

수 10개를 입력받은 뒤, 이를 42로 나눈 나머지를 구한다. 그 다음 서로 다른 값이 몇 개 있는지 출력하는 프로그램을 작성하시오.

입력

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

출력

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

제한

시간 제한 : 1초 / 메모리 제한 : 128MB

---

1. 어떻게 풀까?

1-1) 서로 다른 값을 어떻게 처리할까?

서로 다른 나머지의 값으로 가능한 것이 몇개가 가능한지 알아보는 문제이다.

42라는 고정된 값으로 나누었으므로, 가능한 나머지는 0부터 41까지이다. 이러한 특징을 이용하여 두 가지 방법으로 문제를 풀 수 있다.

 

1. 구현에 초점을 둔 방법

크기가 42인 bool 배열을 선언한 다음, 입력으로 들어온 수의 나머지의 index를 true로 바꾸어준 다음, 마지막에 true의 개수를 세어주면 된다.

이를 나타내면 다음과 같이 작성할 수 있다.

 

bool rem[42];
int cnt = 10;
while (cnt--){
    int num; cin >> num;
    rem[num%42] = true;
}
 
int ans = 0;
for (int i = 0; i < 42; i++) {
    if (rem[i]) { ans++; }
}

 

2. 특별한 컨테이너(set)를 사용하는 방법

C++의 컨테이너 형태 중 set이라는 것이 있다.

set의 가장 큰 특징은 중복을 허락하지 않는다는 점이 있고, 이를 활용하면 중복되는 항목이 들어가도 set형이 무시를 하기에 중복을 방지할 수 있다. 이를 이용하여 중복되지 않게 나머지를 set형에 담으면 다음과 같다.

마지막으로 set형의 크기를 출력해주면 끝!

 

set<int> table;
int cnt = 10;
while (cnt--){
    int num; cin >> num;
    table.insert(num % 42);
}
 
cout << table.size();

 

2) 최종 코드

두 번째 방법의 코드를 바탕으로 작성하였다.

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    set<int> table;
    int cnt = 10;
    while (cnt--){
        int num; cin >> num;
        table.insert(num % 42);
    }
 
    cout << table.size();
 
    return 0;
}