C언어 백준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.각각의 나머지를 각 배열에 넣기

 

2. 배열의 나머지를 비교하기

 

 

▼잘못된 코드 

#include <stdio.h>


int main()
{
    int arr[10]; //입력받은 10개의 수를 각각 42로 나눈 나머지를 저장할 배열 선언
    int a = 42;
    
    int Different_remain = 1;// 서로 다른 나머지의 개수 모두 다같아도 1개는 있는 것이므로 default =1  

    printf("----------42로 나눈 나머지 문제\n");
    printf("10개의 수를 입력하시오\n");

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

        scanf("%d", &arr[i]);
        arr[i] = arr[i] % 42; // 입력 값들의 나머지


    }

    for (int j = 0; j <= 9; j++) {
        
        if ( a != arr[j]){
        
        ++Different_remain;


    }

  
    return 0;
}

42를 나누는 수의 나머지는 1~41 까지 밖에 안되는 점

을 고려하여 a = 42로 정의하였다. 

이러면 a는 arr[1]과 무조건 다를 것이고 

이에 따라 Different_remain(서로 다른 나머지 개수) 에는 반드시 1이 추가된다.

그러니 추가된 1을 다시 뺴주면 arr[0]~arr[9] 사이의 서로다른 나머지의 개수를 구할

수 있다. 

예시3에서의 반례가 나온다.

 

따라서 옆자리만 비교할 것이 아니라, 원소당 다른 원소 모두를 비교하는 식의

알고리즘을 짜야겠다는 생각이 들었다.  

 

 

for 문 두개 사용

 

#include <stdio.h>


int main()
{
    int arr[10]; //입력받은 10개의 수를 각각 42로 나눈 나머지를 저장할 배열 선언
    
    
    int Different_remain = 0;

    printf("----------42로 나눈 나머지 문제\n");
    printf("10개의 수를 입력하시오\n");

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

        scanf("%d", &arr[i]);
        arr[i] = arr[i] % 42; // 입력 값들의 나머지

    }

    for (int j = 0; j <= 9; j++) {
        int count = 0;

        for (int k = j + 1; k <= 9; k++) {
        
            if (arr[j] == arr[k]) {
                ++count;
            }
        
        }
        if (count == 0) {
            ++Different_remain;
        }

    }

    printf("%d", Different_remain);
    return 0;

}

이렇게 순차적으로 비교하는 식을 쓰니 해결이 되었다

 

 

해결에 어려움을 느낀 이유

 

1) 순차적으로 계산해야하는데 어떻게 할 지 몰랐음 

 배열 자체를 비교하는 아이디어에는 for 문을 두번 사용하자.

 

2) count ++ 해주고 , count = 0 일 때가 같다 라는 아이디어 자체가 직관적으로 와닿지 않았음

컴퓨터의 관점에서 핵심은 그렇다/아니다 ( 1/0) 이라는 점에 주목해서 문제를 해결해 나가자