[C/Baekjoon] 백준 3052번(4-8) : 나머지

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

 

 

 

 

#include <stdio.h>

int main() {
    int myary[10];
    for(int i = 0; i<10; i++) {
        int a;
        scanf("%d",&a);
        myary[i] = a;
    }
    
    int dif = 0;
    int ary2[10] = {0};
    int fini[999] = {0}; //처리안되었으면 0, 처리되었으면 1
    
    for(int j = 0; j<10; j++) {
        ary2[j] = myary[j]%42;
        if(fini[ary2[j]] == 0) {
            fini[ary2[j]] = 1;
            dif++;
        }        
    }
    
    printf("%d",dif);
    
    return 0;
}

 

[주목할만한 부분]

배열 안에 배열을 넣는 방법으로 풀어 보자.

fini[999] 배열을 0~999가 적힌 버킷(양동이) 999개로 생각하자.
버킷에는 0, 1밖에 들어갈 수 없다.

a의 범위가 0~1000의 정수이므로 나머지는 0~999가 될 수 있다.
따라서 ary2[] 배열의 요소에 들어갈 수 있는 수는 0~999이며,
이에 따라 처리된 fini[999] 의 크기는 999이고,
이는 ary2[] 배열 각 요소에 저장된 숫자에 하나씩 대응된다.


fini[]의 초기 상태는 모두 0이 들어가 있다.
ary2[] 배열의 각 요소를 돌며 
예를 들어 ary2[1] = 33 이라면, fini[33] 즉 33이 적힌 버킷에 0 대신 1을 넣고, dif 를 1 증가시킨다.
이미 버킷에 들어간 것이 1이라면 아무 일도 일어나지 않는다.

이런 식으로 0 대신 1을 넣은 횟수를 세면, 그것이 서로 다른 나머지 값의 개수일 것이다.