백준 25487번 [단순한 문제 (Large)](C++) -yes6686- 티스토리

백준 문제 풀이: 25487 (단순한 문제 Large)

---

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

문제 설명:

세 양의 정수 a, b, c가 주어질 때, 다음 조건을 만족하는 정수 쌍 \( (x, y, z) \)의 개수를 구하는 문제입니다:

• ( 1 <= x <= a )
• ( 1 <= y <= b )
• ( 1 <= z <= c )
• ( (x mod y) = (y mod z) = (z mod x) )

A mod B는 ( A )를 ( B )로 나눈 나머지를 의미합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

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

    int T; // 테스트 케이스 수
    cin >> T;

    while (T--) {
        int a, b, c;
        cin >> a >> b >> c; // 세 정수 입력
        cout << min({a, b, c}) << '\n'; // 최소값 출력
    }

    return 0;
}

---

문제 조건 정리

주어진 조건:

(x mod y) = (y mod z) = (z mod x)

1. **나머지의 정의에 따라:**

   (x mod y) ≤ x, (y mod z) ≤ y, (z mod x) ≤ z

   - 나머지는 나눈 수보다 작거나 같으므로 위 조건이 항상 성립합니다.
2. **모순 확인:**(x mod y) == x가 성립하려면 \( x < y \)여야 합니다. 같은 원리로:(y mod z) == y → y < z (z mod x) == z → z < x
3. 하지만 이 경우, y > x > z > y가 되어 **모순**이 발생합니다. 따라서 이 경우는 제외됩니다.
4. **남은 조건:**모순이 제외되면, 다음 조건만 남습니다:
5. (x mod y) < x, (y mod z) < y, (z mod x) < z
6. **나머지가 작아지는 조건:**나머지가 원래 수보다 작아지려면:위 조건이 동시에 성립하려면:x ≥ y ≥ z ≥ x결국 **x = y = z**여야 합니다.
7. (x mod y) < x → x ≥ y (y mod z) < y → y ≥ z (z mod x) < z → z ≥ x
8. **결론:**조건 (x mod y) = (y mod z) = (z mod x)를 만족하려면:이 경우의 수는 세 수 a, b, c 중 **최솟값**에 해당합니다.
9. x = y = z

---

코드 설명

• 입력 처리: 여러 개의 테스트 케이스를 while (T--)를 사용해 반복 처리합니다.
• 최솟값 구하기: min({a, b, c})를 사용하여 세 정수 중 가장 작은 값을 구합니다.
• 시간 복잡도: 각 테스트 케이스당 상수 시간에 처리되므로 **O(T)**입니다.

---

입출력 예시

• 입력 예시:

  3  
  1 2 3  
  5 2 4  
  10 10 10

• 출력 예시:

  1  
  2  
  10

---

최종 정리

주어진 조건 (x mod y) = (y mod z) = (z mod x)를 만족하는 경우는 **x = y = z**입니다. 결국, 결과는 세 수 a, b, c 중 **최솟값**입니다.