백준 11947번 [이런 반전이](C++) -yes6686- 티스토리

백준 문제 풀이: 11947 (이런 반전이)

---

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

문제 설명:

주어진 정수 N에 대해 다음 조건을 만족하는 수를 찾아야 합니다:

1. 0부터 9까지의 숫자를 반전시킨 **보수 수**를 계산합니다. 예: 123 → 876.
2. 정수 N과 그 보수 수의 곱을 구합니다.
3. 이 중 **최대 곱**을 출력합니다.

입력으로 주어진 여러 테스트 케이스에 대해 결과를 출력합니다.

---

문제 해결 코드

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

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

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

    while (T--) {
        string n;
        cin >> n;

        // 입력이 10억인 경우 특별 처리
        if (n == "1000000000") {
            cout << "8999999999000000000\n";
            continue;
        }

        // 기준이 되는 값 k = 5 followed by (n.size() - 1) zeros
        string k = "5";
        for (int i = 0; i < n.size() - 1; i++) {
            k += '0';
        }

        long long nn = stoll(n); // 입력 N을 숫자로 변환
        long long kk = stoll(k); // k를 숫자로 변환

        long long ss = 0; // 보수 값을 계산
        if (nn < kk) { // N이 k보다 작을 때
            for (int i = 0; i < n.size(); i++) {
                ss *= 10;
                ss += 9 - (n[i] - '0');
            }
            cout << nn * ss << '\n'; // N과 보수 값의 곱 출력
        } else { // N이 k 이상일 때
            for (int i = 0; i < k.size(); i++) {
                ss *= 10;
                ss += 9 - (k[i] - '0');
            }
            cout << kk * ss << '\n'; // k와 보수 값의 곱 출력
        }
    }

    return 0;
}

---

코드 설명

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

• 보수 수 계산: 입력 숫자 N 또는 기준값 k를 반전시켜 9에서 각 자릿수를 빼줍니다.
• 기준 값 설정: k = 5 * 10^(n.size() - 1): 입력 길이 기준으로 '5' 뒤에 0을 붙여 생성합니다.
• 조건 분기:
  • N < k: 입력 N의 보수를 구해 곱셈을 수행합니다.
  • N ≥ k: 기준 값 k의 보수를 구해 곱셈을 수행합니다.
• 특수 처리: 입력이 **1000000000**인 경우에는 고정된 값을 출력합니다.

시간 복잡도 분석

• 각 숫자의 길이를 n이라고 하면 보수를 구하는 작업의 시간 복잡도는 **O(n)**입니다.
• 총 **T**개의 테스트 케이스에 대해 시간 복잡도는 **O(T ⋅ n)**입니다.

---

결과

입력된 숫자에 대해 최댓값이 되는 곱을 출력합니다.

• 입력 예시:

  3  
  12  
  1000  
  1000000000

• 출력 예시:

  936  
  8991000  
  8999999999000000000

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