백준 12845번 [문서 검색](C++) -yes6686- 티스토리

백준 문제 풀이: 12845 [모두의 마법]

---

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

문제 설명:

게임에서 n개의 카드를 가지고 있을 때, 두 카드를 선택해 합쳐 점수를 얻고, 새로운 카드의 레벨은 더 높은 카드의 레벨로 유지됩니다. 최대 점수를 얻기 위해 어떤 순서로 카드를 합쳐야 하는지 계산합니다.

---

문제 해결 코드

// 백준 12845 - 모두의 마법
#include <iostream>
#include <algorithm>
using namespace std;

int arr[1001]; // 카드 레벨 배열

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

    int n;
    cin >> n; // 카드 개수

    int maxLevel = 0; // 가장 높은 레벨
    int totalScore = 0; // 점수 합산

    // 카드 레벨 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        maxLevel = max(maxLevel, arr[i]);
        totalScore += arr[i];
    }

    // 최대 점수 계산
    int result = (totalScore - maxLevel) + (maxLevel * (n - 1));
    cout << result << '\n';

    return 0;
}

---

코드 설명

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

• 핵심 알고리즘:
  • 가장 높은 레벨의 카드를 최대한 활용하여 높은 점수를 얻습니다.
  • 모든 카드의 합에서 가장 높은 카드의 레벨만 남기고, 나머지 카드 레벨의 합을 점수에 추가합니다.
• 구현 세부사항:
  • maxLevel: 카드 레벨 중 최대값을 추적합니다.
  • totalScore: 모든 카드 레벨의 합을 계산합니다.
  • 최대 점수는 (totalScore - maxLevel) + (maxLevel * (n - 1))로 계산됩니다.
• 시간 복잡도 분석:
  • 카드 입력 및 최대값 찾기: O(n)
  • 최대 점수 계산: O(1)
  • 총 시간 복잡도: O(n)

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

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