백준 10539번 [수빈이와 수열](C++) -yes6686- 티스토리

백준 문제 풀이: 10539 (수빈이와 수열)

---

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

문제 설명:

수빈이는 수열 **B**를 알고 있고, 이 수열을 통해 수열 **A**를 구하고자 합니다. 수열 **B**는 수열 **A**를 통해 다음과 같은 공식으로 정의됩니다: B[i] = (A[0] + A[1] + ... + A[i]) / (i + 1) 수열 **A**를 구하는 것이 목표입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arrA[101]; // 수열 A를 저장하는 배열
int arrB[101]; // 수열 B를 저장하는 배열

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

    int n;
    cin >> n; // 수열의 길이 입력

    // 수열 B 입력
    for (int i = 0; i < n; i++) {
        cin >> arrB[i];
    }

    // 수열 A의 첫 번째 항은 B의 첫 번째 항과 동일
    arrA[0] = arrB[0];
    cout << arrA[0] << ' ';

    // 나머지 항 계산
    for (int i = 1; i < n; i++) {
        int sum = 0;

        // A[0]부터 A[i-1]까지의 합 구하기
        for (int j = 0; j < i; j++) {
            sum += arrA[j];
        }

        // A[i] 계산: B[i] * (i + 1) - sum
        arrA[i] = (arrB[i] * (i + 1)) - sum;
        cout << arrA[i] << ' ';
    }

    return 0;
}

---

코드 설명

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

• 핵심 알고리즘: 주어진 수열 **B**를 이용해 수열 **A**를 하나씩 구합니다. 공식 B[i] = (A[0] + A[1] + ... + A[i]) / (i + 1)를 변형하여 다음 항을 계산합니다.
• 구현 세부사항:
  • 수열 A의 첫 번째 항은 A[0] = B[0]입니다.
  • 나머지 항 A[i]는 이전 항들의 합 sum과 다음 공식으로 계산됩니다:

    A[i] = (B[i] * (i + 1)) - sum

  • 이전 항들의 합 sum은 A[0]부터 A[i-1]까지의 합입니다.
• 시간 복잡도 분석:
  • 각 i에 대해 합 sum을 구하는데 O(i)가 소요됩니다.
  • 전체 시간 복잡도는 O(n²)입니다.
  • 입력의 최대 길이가 100이므로 O(n²) 풀이도 문제 없이 작동합니다.

---

결과

주어진 수열 **B**에 대한 수열 **A**를 정확하게 구하고 출력합니다.

• 입력 예시:

  4  
  1 2 2 3

• 출력 예시:

  1 3 1 3

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