백준 3052 번 문제 풀이 C++ :나머지

#39. 백준 3052번 문제 풀이: 나머지

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

입력/출력

--입력--
39
40
41
42
43
44
82
83
84
85
--출력--
6

문제풀이+해설

이 문제의 풀이 과정은
 1. 숫자열의 나머지를 구한다.
 2. 나머지들을 저정해 둔다.
 3. 나머지들 중에 서로 다른 숫자의 갯수를 구한다.

여기서 핵심은 42로 나눈 나머지라고 했으므로, 나머지의 최대값은 41 이다.
즉 크리가 42인 배열을 만들어 해당 배열인덱스값을 나머지값이라고 가정하여, 해당인덱스 배열의 값을 1로 넣어주면 된다.
최종적으로 배열중에서 1의 값을 가진 배열의 개수가 다른 숫자의 나머지가 된다.

예) 3까지 저장할 수 있는 배열이 있다면.
  ⓞ ① ②  ③  : 배열 인덱스값이 나머지 숫자라 가정한다.
 [0, 1, 0, 1] : 인덱스 ① , ③ 값이 1이므로, 1 과 3을 나머지라 간주한다.

*핵심: 배열의 인덱스값을 숫자값이라고 가정하고 사용하는 알고리즘이 많다.

code sol.

코드편집/실행

#include <iostream>
using namespace std;

int main() {
  int i, v, count = 0;
  int a[42] = {0};
  // 나머지 값을 a의 인덱스로 가정해서 저장할 배열.
  // 42로 나누므로 최대값은 41 이므로, 0으로 초기화된 42개 항목의 배열 생성
  for(i = 0; i < 10; i++) { // 10회 루프
    cin >> v; // 숫자를 입력받고 정수로 변환해서 v에 대입
    a[v%42] = 1; // a 배열에서 나머지에 해당하는 인덱스 항목에 1을 대입
  }
  for(i = 0; i < 42; i++) {
    if(a[i] == 1) count ++; // 나머지가 있는 항목은 카운트
  }
  
  cout << count; // 카운트(다른 숫자 나머지 갯수) 출력
  return 0;
}