백준 17509번 [And the Winner Is... Ourselves!](C++) -yes6686- 티스토리

백준 문제 풀이: 17509 [And the Winner Is... Ourselves!]

---

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

문제 설명:

11개의 문제를 푸는 데 걸리는 시간과 각 문제의 벌점이 주어진다. 문제를 푸는 순서를 적절히 정해 총 점수를 최소화하도록 한다. 총 점수는 다음과 같이 계산된다:

• 문제를 푸는 데 걸린 시간의 누적 합
• 벌점에 20을 곱한 값을 누적 시간에 더한 값

입력:

• 11개의 줄에 걸쳐 각 문제를 푸는 데 걸리는 시간과 벌점이 공백으로 구분되어 주어진다.

출력:

• 최소화된 총 점수를 출력한다.

---

문제 해결 코드

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

pair<int, int> arr[11];

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

    for (int i = 0; i < 11; i++) {
        cin >> arr[i].first >> arr[i].second; // 문제를 푸는 데 걸리는 시간과 벌점 입력
    }
    sort(arr, arr + 11); // 시간을 기준으로 오름차순 정렬

    int ans = 0; // 총 점수
    int t = 0;   // 누적 시간
    for (int i = 0; i < 11; i++) {
        t += arr[i].first; // 현재 문제를 푸는 데 걸리는 시간 추가
        ans += t + (20 * arr[i].second); // 총 점수 계산
    }
    cout << ans << '\n'; // 최소화된 총 점수 출력
    return 0;
}

예제

입력:
10 1
20 2
15 3
30 4
5 2
25 1
40 0
35 3
50 5
45 2
60 4

출력:
1975

---

코드 설명

• 입력 처리: 각 문제를 푸는 데 걸리는 시간과 벌점을 배열에 저장합니다.
• 정렬: 문제를 푸는 시간을 기준으로 오름차순 정렬하여 최소 누적 시간을 얻습니다.
• 총 점수 계산: 누적 시간과 벌점을 이용해 총 점수를 계산합니다.

시간 복잡도

• 입력 정렬: O(n log n)
• 총 점수 계산: O(n)
• 전체 시간 복잡도: O(n log n)

---

결과

위 코드는 주어진 조건에 따라 문제를 푸는 순서를 최적화하여 최소 총 점수를 정확히 계산합니다. 개선점이나 다른 접근 방식에 대한 논의는 환영합니다!