BOJ 26101번 - 링크와 스타트 2

일상

hijkl2e 2023. 2. 10. 03:25

26101번: 링크와 스타트 2

첫째 줄에 N(4 ≤ N ≤ 400)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100

www.acmicpc.net

귀찮기 때문에 구체적인 풀이는 작성하지 않을 것이고 힌트만 몇 개 남긴다.

HINT 1

knapsack dp와 bitset 태그가 붙어 있음에 주목하자.

HINT 2

먼저 26607번을 풀어 보자. 잘 모르겠다면 에디토리얼을 참고하자.

HINT 3

26607번을 bitset으로 풀어 보자.

HINT 4

그 다음에는 21844번을 풀어 보자. 잘 모르겠다면 에디토리얼을 참고하자.

HINT 5

21844번을 크기가 5e5인 bitset으로 풀어 보자.

HINT 6

본 문제는 크기가 16e6인 bitset으로 풀이할 수 있으며 업데이트는 N번 이루어진다.

참고로 26101번을 풀면 26100번이 따라 온다.

끝