엘리스 알고리즘 코드 챌린지, 예선 8일 차 문제

강의는 다이나믹 프로그래밍이다. 전날의 영상과 동일하다.

강의와 문제는 큰 관련이 있다. dp를 사용하면 된다.

문제는 강림제(인기가 넘쳐흘러, https://www.acmicpc.net/problem/17258, 플4였는데 골1로 내려감, 골1?, 당일 저녁 기준 맞힌 사람 170명, 풀이 3시간30분)이고 백준 문제와 동일하다.

풀이는 dp를 쓰면 된다.
입력 예시에서 시간대별로 추가적으로 필요한 인원을 배열로 나타내면 [0(필러 인덱스), 2, 2, 1, 1, 0, 0, 0, 0, 0, 1, 1]이고(이때 쿼리와 배열이 크다면 imos법을 쓰는 게 빠르다.) 주어진 입력과 이 배열은 동치이니 변환하더라도 문제를 풀 수 있다. 0을 기준으로 partition을 나누면 [[0], [2, 2, 1, 1], [0, 0, 0, 0, 0], [1, 1]]이고 친구들을 제외한 신도가 T명 이상이면 친구들이 바로 나가버리기 때문에 partition을 나눠도 문제를 풀 수 있고 서로 다른 partition은 서로 다른 문제이니 더 쉽게 풀 수 있다. 냅색 문제에서 했듯이

# dp[0][0] = 0번째 구간에서 0 이하인 원소의 개수  # 초기값
# dp[i][k] = 0..i번째 구간을 쓰고 그 구간에서 총 k명을 쓸 때 최대 시간
#          = max(i번째구간에서now이하인원소의개수 + dp[i-1][k-now])
#            단 now는 i번째 구간에서 쓰는 인원, k-now은 0..i-1번째 구간에서 쓰는 인원

위와 같은 점화식을 사용한다. "i번째구간에서now이하인원소의개수"는 누적합을 이용해 빠르게 구할 수 있고 저장 후 인덱싱으로 불러오기만 하면 된다. 그 후 최댓값에서 인덱싱을 편하게 하기 위해 만든 0시~1시의 가짜 인덱스의 밸류 0 한 개를 뺀 max(dp)-1를 출력하면 된다. partition을 상술한 예시처럼 0을 포함하고 만들면 그대로 출력하면 되고, partition을 0을 빼고 만들 경우([[2, 2, 1, 1], [1, 1]]처럼) 길이가 0이면 인덱스에러가 나기 때문에 길이가 0이라면 바로 partition을 만들기 이전의 계수 배열에서 0의 개수를 센 뒤 출력하면 된다. 점화식과 냅색 발상이 어려운 것이지 코드는 쉬우므로 코드는 생략한다.

# 구간 나누지 않고 전체 time을 순회하고 0을 만나는 순간 분기
# dp[0][0][K] = 1  # 초기값. needed[time=0]=0이라서 now=0 고정이고 이때 값은 1
# dp[time][now][left] = time 시점에서 now를 쓰고
#                       과거 사용, 현재 사용 빼고 left가 남았을 때 최대 시간
#                     = 점화식[
#                       dp[t][0][left] = dp[t-1][0][left]  # 0->0
#                       dp[t][now][left] = dp[t-1][0][now + left]  # 0->1
#                       dp[t][0][left] = max(
#                           dp[t-1][temp_now][left] for temp_now in range(K+1)
#						)  # 1->0
#                       dp[t][now][left] = dp[t-1][now][left]  # 1->1
#                       ] 중 하나를 사용한 뒤
#                       추가로 dp[t][now][left] += int(needed[t] <= now)

위는 솔루션의 코드이다. 삼중반복문의 발상이 어렵고 분기 4개에 해당하는 점화식의 발상과 구현이 어렵다. 나의 풀이에서는 0->1, 1->0만 봤으면 됐고 1->1, 0->0은 "i번째구간에서now이하인원소의개수"을 이용해 동일한 left지만 서로 다른 now 중 최댓값을 빠르게 구할 수 있었다. 설명이 부실하긴 하지만 https://ps.mjstudio.net/boj-17258을 참고하라.

다시 난도가 상승했다. 현재까지 만점자 중 50번째로 빨리 푼 사람이 12:26분, 100번째로 빨리 푼 사람이 19:37분에 풀었다. 대충 추세를 보면 당일 내에 푼 사람은 130명 정도가 될 듯하다.