백준 12971번 [숫자 놀이](C++) -yes6686- 티스토리

백준 문제 풀이: 12971 (숫자 놀이)

---

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

문제 설명:

세 개의 주어진 나머지 조건을 만족하는 가장 작은 양의 정수를 찾는 문제입니다. - i % p1 == x1 - i % p2 == x2 - i % p3 == x3 여기서 p1, p2, p3는 각각의 나머지 연산의 모듈로 값입니다. 만약 조건을 만족하는 값이 존재하지 않으면 **-1**을 출력해야 합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int p1, p2, p3, x1, x2, x3; // 입력 값
    cin >> p1 >> p2 >> p3 >> x1 >> x2 >> x3;

    // 모든 가능한 값 i를 순회하면서 조건 검사
    for (int i = 1; i <= p1 * p2 * p3; i++) {
        if ((i % p1 == x1) && (i % p2 == x2) && (i % p3 == x3)) {
            cout << i << '\n'; // 조건을 만족하는 가장 작은 값 출력
            return 0;
        }
    }

    // 조건을 만족하는 값이 없을 경우
    cout << -1 << '\n';
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 브루트포스 탐색: 1부터 p1 × p2 × p3까지 모든 값을 순회하며 조건을 만족하는지를 확인합니다.
• 조건 검사: 각 값 i에 대해 다음 조건이 모두 참인지 확인합니다:
  • i % p1 == x1
  • i % p2 == x2
  • i % p3 == x3
• 최적화: 탐색 범위는 세 나머지의 최소 공배수인 p1 × p2 × p3입니다. 이 범위 안에서 조건을 만족하는 값을 찾으면 바로 반환합니다.

시간 복잡도 분석

• 최대 탐색 범위는 **p1 × p2 × p3**입니다.
• 브루트포스로 모든 값을 확인하므로 시간 복잡도는 **O(p1 × p2 × p3)**입니다.
• 주어진 조건에서 입력이 작기 때문에 효율적으로 수행됩니다.

---

결과

주어진 조건을 만족하는 가장 작은 양의 정수를 출력합니다. 만약 조건을 만족하는 값이 없으면 -1을 출력합니다.

• 입력 예시:

  3 5 7  
  2 4 6

• 출력 예시:

  34

• 입력 예시:

  3 5 7  
  1 2 3

• 출력 예시:

  -1

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