utterances-bot commented 2 years ago

[SWEA] 8935. 스팟마트 (C++, 라이브러리 X) - 유년시절

DP 실전문제 풀이 M개의 봉지 B를 오름차순으로 정렬. dp[n][l][r][take] 설정. (현재 상태에서 최대 과자 개수) n은 N개의 봉지 중에서 n번째 봉지까지 확인한 상태. l은 M개의 봉지 중에서 l개를 가져간 상태. (항상 큰 봉지 먼저 가져감) r은 M개의 봉지 중에서 r개를 버린

https://blog.uniony.me/swea/8935/

ghost commented 2 years ago

r이 M개의 봉지 중에서 버린 봉지의 개수라고 하셨는데, 버린다는 게 어떤 의미인지 이해가 안 되는데 설명해주실 수 있으신가요?

unionyy commented 2 years ago

@steve7867 문제가 정확히 기억이 안나서 어렴풋이 기억나는 대로 말씀 드립니다.

앞에서 부터 봉지를 하나씩 가져가고 버린다고 했을 때에 추가 봉지(M)은 가져가기 위해 놓거나 버리기 위해 놓는다고 볼 수 있습니다.

이때 가져가는 봉지는 클 수록 좋고 버리는 봉지는 작을 수록 좋으니, 봉지를 크기 순으로 정렬해서 가져갈 때에는 큰 봉지 먼저 가져가고 버릴 때에는 작은 봉지 먼저 버립니다.

그러므로 M개의 봉지 중에서 l개를 가져가고 r개를 버린 상태에 남은 추가 봉지(M)는 항상 동일한 상태가 되며, DP를 이용하여 문제를 해결할 수 있게 됩니다.

ghost commented 2 years ago

@unionyy 무슨 말씀인지 이해했습니다. 답변해주셔서 감사합니다~~

unionyy / blog

swea/8935/ #21

[SWEA] 8935. 스팟마트 (C++, 라이브러리 X) - 유년시절