BOJ_17224 APC는 왜 서브태스크 대회가 되었을까?

• TOC {:toc}

이 글은 백준 온라인 저지의 17224번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.08.09 (Python)

import sys
input = sys.stdin.readline
h_count = 0
e_count = 0

N, L, K = map(int, input().split())

for _ in range(N):
    e, h = map(int, input().split())
    if h <= L:
        h_count += 1
    elif e <= L:
        e_count += 1
    else:
        break

print(min(K, h_count) * 140 + min(e_count, max(K - h_count, 0)) * 100)

아이디어 & 풀이

풀 수 있는 문제 중에서 어려운 문제를 먼저 풀고 풀 수 있는 개수가 남아있으면 쉬운 문제를 마저 풀어야 한다.

• 문제 난이도 ‘값’은 크게 상관없고, 풀 수 있는지 아닌지가 중요하기 때문에 난이도(e.g., 어려운 문제: h, 쉬운 문제: e)별 풀 수 있는 문제의 개수만 h_count , e_count로 관리한다.
• 우선 어려운 문제를 풀 수 있는지 확인하고, 풀지 못하면 쉬운 문제를 풀 수 있는지 확인한다.
• 문제가 쉬운 문제의 난이도로 정렬되어 있어 현재 문제의 쉬운 문제도 풀지 못한다면 더 풀 수 있는 문제가 없기 때문에 입력을 종료한다.

점수는 다음과 같이 계산한다.

• 우선 h_count에 140을 곱한 값을 구한다.
  • h_count가 풀 수 있는 문제의 개수인 K보다 클 수 있기 때문에 min을 이용해 두 수중 작은 값을 선택한다.
• K에서 h_count 값을 뺀 만큼 문제를 마저 풀 수 있기 때문에 그 값에 100을 곱한 결과를 더한다.
  • K > h_count인 경우 K - h_count가 0보다 작을 수 있기 때문에 max를 이용해 K - h_count와 0중 큰 값을 사용한다.
  • 풀 수 있는 쉬운 문제가 (i.e., e_count) K - h_count보다 작을 수 있기 때문에 min을 이용해 두 수중 작은 값을 선택한다.

2023.02.17 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [NLK, ...lines] = input;
const [N, L, K] = NLK.split(" ").map((n) => parseInt(n));

function main() {
    const solved = [];
    lines.forEach((difficulty) => {
        const [easy, hard] = difficulty.split(" ").map((n) => parseInt(n));
        if (hard <= L) {
            solved.push(140);
        } else if (easy <= L) {
            solved.push(100);
        }
    });

    const score = solved
        .sort((a, b) => b - a)
        .slice(0, K)
        .reduce((a, b) => a + b, 0);

    return score;
}

console.log(main());

참고 답안

import sys
input = sys.stdin.readline

N, L, K = map(int, input().split())
p = []
for _ in range(N):
    e, h = map(int, input().split())

    if h <= L:
        p.append(140)
    elif e <= L:
        p.append(100)

print(sum(sorted(p, reverse=True)[:K]))

아이디어 & 풀이

• 각 문제를 풀 수 있을 때 count를 세지 않고 문제 난이도에 따른 점수(h: 140, e: 100)를 리스트 p에 추가한다.
• p를 내림차순으로 정렬한 뒤 K 번째 원소까지만 끊어 그 합을 출력한다.