99클럽 코테 스터디 14일차 TIL [04/17]

[시작]

참여 기간 : 2025/03/31 ~ 2025/04/28

참여 난이도 : 파이썬 / 비기너

⏳ 코테 스터디 진행도 🧱 : [▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰░                 ] 14/29일 (48%)

본 글에서 다룬 문제 : 백준 29723번 브실이의 입시전략

문제 푸는 데 걸린 시간 : 시간 측정이 의미 없을 정도로 오래 걸림 + 구글링함

내 풀이 : 빈도 배열

진짜 너무 피곤해서 간결하게 작성하고 마무리

추후 설명이 추가될 수 있음

튜터님 따라하려고 함수로 코드 구현하는 연습 하니까 로컬에서 5번 정도 넘어짐 ㅠ

고수분들의 풀이를 보고 배워야겠다...

진짜 너무 자고싶었는데 흐름 끊기는게 더 괴로울 거ㅅ 같아씀...

 

 

 

 

[오늘의 문제]

 

 

 

[문제 해석]

N 개의 과목 중, 브실대가 평가에 활용할 과목은 정확히 M 개

그중 K 개 과목 이름은 이미 ‘필수’라고 공개돼 있다.

필수 K 과목 + 나머지(N‑K) 과목 중 (M‑K) 개를 더 뽑아 총점을 낸다.

브실이는 최소 점수(최악)와 최대 점수(최선)를 알고 싶다.

 

 

 

[구현]

▶ 구현할 코드 흐름(입력)

1. 과목 총 N, 브실대가 요구하는 과목 수 M, 이미 공개된 필수 과목 수 K 입력
2. N 줄 동안: 과목 이름 name 과 점수 p를 딕셔너리에 저장
   • {이름: 점수}
3. K 줄 동안: 필수 과목 이름을 리스트에 저장

 

▶ 구현할 코드 흐름(로직)

1. 필수 과목 총점계산
2. 선택 후보 점수 빈도표 생성
3. 추가로 뽑아야 할 과목 수
4. 최소/최대 합 구하기
5. 최종 점수

 

▶ 구현할 코드 흐름(출력)

1. 공백 하나로 구분해 "최소 점수 최대 점수" 순서로 출력

 

 

 

[코드]

import sys

def solve() -> None:
    input = sys.stdin.readline          # 백준은 이거 국룰
    N, M, K = map(int, input().split()) # 수강 과목 수, 평가 과목 수, 공개된 과목 수

    score_of = {}                       # {과목이름: 점수}
    for _ in range(N):
        name, p = input().split()
        score_of[name] = int(p)

    mandatory = [input().strip() for _ in range(K)]   # 필수 과목 이름 K개

    # (1) 필수 과목 총점
    base = sum(score_of[name] for name in mandatory)

    # (2) 선택 후보 점수 빈도 모음
    freq = [0] * 101                    # 점수는 0~100
    for name, p in score_of.items():
        if name not in mandatory:       # 필수 과목은 제외함
            freq[p] += 1

    need = M - K                        # 추가로 뽑아야 할 과목 수 (0이면 그대로 base임)

    # (3) 최소 최대 가산점 계산
    def k_smallest_sum(k: int) -> int:  # 가장 작은 k개 점수 합
        s = 0
        for score in range(101):
            if k == 0: break
            take = min(k, freq[score])
            s   += score * take
            k   -= take
        return s

    def k_largest_sum(k: int) -> int:   # 가장 큰 k개 점수 합
        s = 0
        for score in range(100, -1, -1):
            if k == 0: break
            take = min(k, freq[score])
            s   += score * take
            k   -= take
        return s

    min_total = base + k_smallest_sum(need)
    max_total = base + k_largest_sum(need)

    print(min_total, max_total)

if __name__ == "__main__":
    solve()

작성하다가 머리에 침대가 너무 아른거려서 괴로웠다...

 

 

 

[제출 결과]

맞은게 맞은 게 아님

다시 작성해라고 하면 틀릴 거다 아마

 

 

 

[시간복잡도]

총 시간 복잡도는 O(N)

설명할 힘이 없어 유능한 gpt 센세에게 설명을 부탁했다.

 

• K ≤ M ≤ N 이므로 K ≤ N.
• 상수 202는 입력 크기와 무관하므로 빅‑O에서 제거
• N = 브실이가 수강한 과목 수, 최대 10 000

결론은 O(N)

 

 

 

 

 

[다른 접근 방법]

나는 빈도 배열을 사용했다.

빈도 배열로 코드 작성하기 전에는 전체 정렬하는 방법으로 코드를 작성했는데

계속 에러나고 이상한 output이 나오길래(사실 내가 어디서 뭘 잘못했으니... 그러지 않았나...)

빈도 배열을 방법을 시도했다.

따라서 그냥 전체 정렬하는 방법만 떠오른다.

다른 건 아직 몰루 ㅠㅠ

 

 

 

[회고]

잠을 이겨내면서 억지로 푸느라 코드가 스파게티가 되어버렸다.

이건 주말에 다시 풀어보면서 복기를 해야지 머리에 남을 것 같다.

평소 하던대로 코드를 작성하려고 하니 비효율적인 것 같아서 '빈도 배열'을 사용했다.

또한 나중에 복잡한 코드를 작성할 때를 대비해서 함수를 사용하는 습관을 들이기 위해서 함수로 구현했다.