[BaekJoon] 백준 17224 APC는 왜 서브태스크 대회가 되었을까? (Python / 파이썬)

BaekJoon 백준 17224 APC는 왜 서브 태스크 대회가 되었을까? 문제는 어떤 문제에 대해 쉬운 버전을 해결한다면 100점을 얻고, 어려운 버전을 해결한다면 140점을 얻게 된다. APC에 참가했다면 최대 몇 점을 얻을 수 있었을지 구하는 문제이다. 난이도는 Bronze 1이다.

 

BaekJoon 17224 APC는 왜 서브 태스크 대회가 되었을까? 문제 정보

출처

- https://www.acmicpc.net/problem/17224

알고리즘 분류

- 그리디 greedy 탐욕 알고리즘

난이도

- 브론즈 1 / Bronze 1

 

APC는 왜 서브 태스크 대회가 되었을까? 문제 요약

• 하나의 문제를 제한조건을 통해 쉬운 버전과 어려운 버전으로 나누어 쉬운 버전만 맞더라도 부분점수를 주는 서브 태스크 문제로 대회를 구성하는 것이다. 또한 이렇게 만들어진 문제를 쉬운 버전의 난이도 순으로 배치하려 한다.
• 어떤 문제에 대해 쉬운 버전을 해결한다면 100점을 얻고, 어려운 버전을 해결한다면 여기에 40점을 더 받아 140점을 얻게 된다. 어려운 버전을 해결하면 쉬운 버전도 같이 풀리게 되므로, 한 문제를 해결한 것으로 계산한다.
• 현정이는 L 만큼의 역량을 가지고 있어 L보다 작거나 같은 난이도의 문제를 풀 수 있다. 또한 현정이는 코딩이 느리기 때문에 대회 시간이 부족해 K개보다 많은 문제는 해결할 수 없다.
• 현정이가 APC에 참가했다면 최대 몇 점을 얻을 수 있었을지를 구하여 출력한다.
• 문제의 개수 N, 현정이의 역량 L, 현정이가 대회 중에 풀 수 있는 문제의 최대 개수 K, 쉬운 버전의 난이도 sub1, 어려운 버전의 난이도 sub2가 주어진다. (1 ≤ N ≤ 100, 1 ≤ L ≤ 50, 1 ≤ sub1 ≤ sub2 ≤ 50)

 

문제 풀이 과정

1. 문제 별 득점을 저장할 리스트를 정의한다.
2. 문제 별로 난이도와 현정이의 역량을 비교하여,
3. 어려운 문제 난이도보다 역량이 크거나 같아서 풀 수 있다면 140점을 저장한다.
4. 어려운 문제는 풀지 못하고 쉬운 문제 난이도보다 역량이 크거나 같아서 풀 수 있다면 100점을 저장한다.
5. 아예 못 풀면 그냥 넘어간다.
6. 모든 문제에 대한 득점을 구했으면 최대 득점 점수를 구해야 하므로 점수들을 정렬한 후, 리스트의 뒤에서부터 K개의 합을 구하여 출력한다.

현정이가 얻을 수 있는 "최고" 점수 이므로 K개 풀 때까지만 반복문을 돌리면 안 되고, 모두 풀었다고 가정 한 뒤, 최대 득점을 구해야 한다.  (문제 자세히 읽기!)

 

코드 및 설명

N, L, K = map(int, input().split())
score = [0] * N  # 문제 별 점수
problem = []
for _ in range(N):
    problem.append(list(map(int, input().split())))

for i in range(N):
    # 어려운 문제를 풀 역량이 되면
    if problem[i][1] <= L:
        score[i] = 140
    # 어려운 문제는 못 풀고 쉬운 문제를 풀 수 있으면
    elif problem[i][0] <= L < problem[i][1]:
        score[i] = 100

print(sum(sorted(score)[:-(K + 1):-1]))

---

BaekJoon 백준 17224 APC는 왜 서브 태스크 대회가 되었을까? 문제를 파이썬 python으로 풀어보았다. greedy 탐욕 그리디 알고리즘에 관한 문제로 난이도는 Bronze 브론즈 1이다.