DP 역추적 썸네일형 리스트형 BOJ)12019 동아리방 청소! 문제:icpc.me/12019 동아리방에 사람들이 들어올때마다 더러움이 누적되고 사람들은 더러움만큼 불쾌함을 느끼게 될 때 N일동안 딱 M번만 청소가 가능하다. N일 동안 들어온 사람 수가 주어질 때 사람들이 느끼는 총 불쾌함의 최솟값을 구하는 문제이다. 우리는 다이나믹 프로그래밍을 통하여 답을 구해줄 수 있다. 근데 불쾌함을 계산할때 (그날 들어온 사람 수) x (누적 된 더러움) 이므로 더러움을 날마다 들어오는 사람들의 수의 psum을 통하여 관리해준다. 그리고 psum으로 누적 된 더러움을 계산할 때 그날까지의 psum - 청소한 날의 psum으로 계산해줘야 하기 때문에 dp테이블에 마지막으로 청소한날을 가지고 가야한다. 따라서 dp 테이블은 dp[pos][state][last] 가 되며 의미는 p.. 더보기 이전 1 다음