김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 2128 마지막 조별 시합 파이썬(Python)

문제 링크

딱 봐도 비트마스킹 문제지만, 입력이 작아서 집합으로도 풀리겠다 싶어서 그냥 푼 문제.
그리고 풀고 나서 생각해보니, 이거 딱히 집합조차도 쓸 필요 없지 않나 싶다.
풀이에서 집합의 메리트를 활용한 부분이 크게 없기 때문…
그런데 후술하겠지만, 알고 보니 비트마스킹을 쓰면 정말 간단하게 풀 방법이 있더라.
n은 최대 1000이고 d는 최대 15이므로 크게 어렵진 않다.
15로 가능한 조합의 수 중 제일 큰 건 기껏해야 \(_{15}C_{7} = 6435\)이고, 거기에 대해서 각 문제(최대 15개)를 풀 수 있는 학생들(최대 1000명)이 다른 문제도 풀 수 있는지만 검사하면 된다.
그러니까 가능한 k개 문제의 조합을 전부 구해서, 그 문제를 풀 수 있는 학생들에 대해, 그 학생들 중 다른 문제는 못 풀고 오직 그 조합의 문제만 풀 수 있는 학생들의 수만 더해주면 된다.
그런데, 이거 비트마스킹을 쓰면 정말 아름답고 편리하게 구할 수 있는데, 학생들이 풀 수 있는 문제의 비트 집합과 조합으로 나오는 비트 집합을 OR 연산을 하면 된다.
그때 결과가 조합으로 나온 비트 집합과 같다면, 그 학생은 조합 안에 들어올 수 있다.
왜냐하면 연산의 결과가 원래 조합으로 나온 비트와 같다는 것은 조합에 있는 문제이거나, 조합에 없고 학생도 못 푸는 문제이거나 둘 중 하나이기 때문이다.
편하려고 집합을 쓴 건데 외려 돌아간 결과가 된 셈.
앞으로는 비트마스킹도 자주 쓰고 숙달할 필요가 있겠다.

#!python

from sys import stdin
from itertools import combinations
input = stdin.readline

n, d, k = map(int, input().split())
# student[i]는 i번 학생이 풀 수 있는 문제들
# problem[i]는 i번 문제를 풀 수 있는 학생들
student = [set() for _ in range(n)]
problem = [set() for _ in range(d)]
# addto는 아무 문제도 못 푸는 학생의 수
addto = 0
# 입력을 받아서 아무 문제도 못 푸는 학생이면 더한다
# 또, students와 problem 리스트를 갱신한다
for i in range(n):
    _, *probs = map(int, input().split())
    if not probs:
        addto += 1
    for p in probs:
        student[i].add(p - 1)
        problem[p-1].add(i)

ans = 0
# 조합으로 가능한 경우의 수 모두 추출
# 반복 횟수는 커봐야 대략 6000 정도다
for j in combinations(range(d), k):
    # checked는 확인한 학생, 그 학생을 다시 확인할 필요는 없으므로
    # 그런데 리스트로 선언하는 게 더 나았을 듯
    # comb는 조합 결과를 집합으로 바꾼 건데 필요한지는 모른다
    checked, comb = set(), set(j)
    # temp는 해당 조합에 부합하는 학생의 수
    temp = 0
    # 조합에 있는 각 문제에 대해
    # 최대 반복횟수는 15
    for l in j:
        # 그 문제를 풀 수 있는 학생들에 대해
        # 최대 반복횟수는 1000인데, 15 * 1000이 아니라 총 1000에 가깝다
        # 왜냐하면 checked 리스트를 통해 이미 검사한 학생은 탈출하기 때문에 하위 루프로 들어가지 않기 때문
        # 물론 checked 리스트를 확인하긴 하지만 안쪽으로 for문을 더 돌지 않는다는 의미
        for s in problem[l]:
            if s in checked:
                continue
            # 확인한 목록에 추가한다
            checked.add(s)
            # 학생이 풀 수 있는 각 문제에 대해
            # 문제 조합에 없는 문제이면 그 학생은 팀에 들어갈 수 없다
            for m in student[s]:
                if m not in comb:
                    break
            # 만약 break를 한 번도 안 했다면 팀에 들어온 것이므로 더해준다
            else:
                temp += 1
    # 조합 내의 모든 문제에 대해 학생의 수를 구했다면 답을 갱신한다
    ans = max(ans, temp)

# 가장 많은 학생이 있는 문제 조합 + 아무 문제도 못 푸는 학생(항상 조에 들어갈 수 있음)
print(ans + addto)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑