Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 주어진 연산을 사용해 배열을 하나의 정수로 줄이는 방법

정수 변수 Number가 입력으로 주어졌다고 가정해 봅시다. 1부터 Number까지 범위의 값들이 임의의 순서로 들어 있는 배열이 있으며, 이 배열에 다음과 같은 연산을 Number−1번 수행합니다.

  • 배열에서 두 개의 요소 A와 B를 선택합니다.
  • A와 B를 배열에서 제거합니다.
  • A² + B², 즉 두 수의 제곱의 합을 배열에 다시 추가합니다.

연산이 모두 끝나면 배열에는 하나의 정수만 남게 됩니다. 목표는 이렇게 만들어진 마지막 값이 가질 수 있는 최댓값을 구하는 것입니다.

우선순위 큐(Priority Queue)를 활용한 접근

최종 결과를 최대화하려면 매 연산마다 배열에 남아 있는 수 중 가장 큰 두 수를 골라 제곱의 합을 만들어야 합니다. 큰 수를 먼저 제곱해 합치면 값이 기하급수적으로 커지므로, 큰 수끼리 조합하는 것이 항상 유리하기 때문입니다.

매번 최댓값 두 개를 빠르게 찾기 위해 우선순위 큐를 사용합니다. 우선순위 큐는 요소를 내림차순으로 자동 정렬하므로 top()을 호출하면 항상 현재 가장 큰 값이 반환됩니다. 알고리즘의 흐름은 다음과 같습니다.

  1. 1부터 N까지의 수를 우선순위 큐에 모두 삽입합니다.
  2. 큐에서 가장 큰 두 수를 꺼내(pop) 각각 제곱한 뒤 더합니다.
  3. 그 합을 다시 큐에 넣고(push), 큐에 요소가 하나만 남을 때까지 반복합니다.
  4. 마지막에 남은 값이 곧 정답입니다.

예제

입력: Number = 2

출력: 배열 축소 후 남은 단일 요소: 5

설명: 배열이 [1, 2]일 때 A=2, B=1을 선택하면 A²+B² = 4+1 = 5가 되며, 마지막으로 남은 값은 5입니다.

입력: Number = 5

출력: 배열 축소 후 남은 단일 요소: 8157330058817

설명: 배열이 [5, 1, 2, 4, 3]일 때 과정은 다음과 같습니다.

  • A=5, B=4 → 25+16 = 41 : {41, 3, 2, 1}
  • A=41, B=3 → 1681+9 = 1690 : {1690, 2, 1}
  • A=1690, B=2 → 2856100+4 = 2856104 : {2856104, 1}
  • A=2856104, B=1 → 8157330058816+1 = 8157330058817 : {8157330058817}

이처럼 값이 매우 빠르게 커지기 때문에 오버플로를 피하려면 결과 타입을 반드시 long long int로 선언해야 합니다.

알고리즘 단계

  • 입력 변수 Number를 받습니다.
  • 결과 저장을 위해 자료형을 long long int(lli)로 정의합니다.
  • reduceArray(int Num) 함수는 입력값을 받아 위 연산을 적용한 결과인 최대 정수를 반환합니다.
  • 우선순위 큐 pQueue를 생성합니다.
  • while 루프를 이용해 1부터 N까지의 수를 pQueue에 삽입합니다.
  • 이제 pQueue에는 1~N이 내림차순으로 정렬되어 있으며 크기는 N입니다.
  • pQueue의 크기가 1보다 큰 동안 while 루프를 반복합니다.
  • var1 = pQueue.top()으로 최댓값을 가져오고 pop() 합니다.
  • var2 = pQueue.top()으로 다음 최댓값을 가져오고 pop() 합니다.
  • var1과 var2를 각각 제곱합니다.
  • var1 + var2를 다시 pQueue에 push 합니다.
  • 루프가 끝나면 top() 요소를 반환합니다.
  • main 함수에서 결과를 출력합니다.

구현 코드 (C++)

#include <bits/stdc++.h>
using namespace std;
#define lli long long int

lli reduceArray(int Num){
    priority_queue<lli> pQueue;
    int i = 1;
    while(i <= Num){
        pQueue.push(i);
        i++;
    }
    while(pQueue.size() > 1){
        lli var1 = pQueue.top();
        pQueue.pop();
        lli var2 = pQueue.top();
        pQueue.pop();
        var1 = var1 * var1;
        var2 = var2 * var2;
        pQueue.push(var1 + var2);
    }
    return pQueue.top();
}

int main(){
    int Number = 5;
    cout << "Single element after array reduction: " << reduceArray(Number);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 생성됩니다.

Single element after array reduction: 8157330058817

복잡도 분석

연산은 총 N−1번 수행되며, 각 연산에서 우선순위 큐의 push/pop은 O(log N)의 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(N log N)이며, 공간 복잡도는 큐에 N개의 요소를 저장하므로 O(N)입니다.