백준 3052번 [나머지](C++)-yes6686- 티스토리

백준 문제 풀이: 3052 [나머지]

---

문제 링크: https://www.acmicpc.net/problem/3052

문제 설명:

10개의 수를 입력받아 각 수를 42로 나눈 나머지를 계산한 뒤, 서로 다른 나머지가 몇 개 있는지 출력하는 프로그램을 작성하세요.

입력 조건:

• 첫째 줄부터 열 번째 줄까지 한 줄에 하나씩 자연수가 주어집니다. 주어지는 수는 0 이상 1,000 이하입니다.

출력 조건:

• 42로 나누었을 때, 서로 다른 나머지가 몇 개 있는지 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    bool remainder[42] = { false }; // 나머지 여부를 저장하는 배열
    int x, count = 0;

    for (int i = 0; i < 10; i++) {
        cin >> x; // 입력된 숫자
        remainder[x % 42] = true; // 나머지에 해당하는 인덱스를 true로 설정
    }

    for (int i = 0; i < 42; i++) {
        if (remainder[i]) { // 나머지가 존재하면 카운트 증가
            count++;
        }
    }

    cout << count << endl; // 서로 다른 나머지의 개수 출력
    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 입력된 숫자들에 대해 나머지를 계산하고, 서로 다른 나머지의 개수를 출력합니다.

• 배열 초기화: `bool remainder[42]` 배열을 초기화하여 나머지가 등장했는지 여부를 기록합니다.
• 나머지 계산:
  • 입력된 각 숫자 `x`에 대해 `x % 42`를 계산하고, 해당 인덱스를 `true`로 설정합니다.
• 결과 계산:
  • `remainder` 배열에서 `true`인 인덱스의 개수를 세어 서로 다른 나머지의 개수를 계산합니다.

시간 복잡도 분석:

• 입력 및 나머지 계산: O(10).
• 나머지 배열 확인: O(42).

따라서 전체 시간 복잡도는 O(1)로 매우 효율적입니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
1
2
3
4
5
6
7
8
9
10

출력:
10

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!