[일반] 제일 최근꺼 div2 D번

[익명(211.202)]

dp 문제 잘 이해가 안가는데 말로 설명좀 가능하신분 계실까요,,

[익명(223.39)]

dp(i, k) = i번째에서 바꿀수 있는 비트가 k개 남았을 때 가능성(true,false) 쯤으로 설정해서 정상적인 숫자라도 만들 수 있는지 검사하고, 그 결과를 역추적해서 최대값을 만듬. 이때 최대한 앞자리에서 큰 숫자가 나오도록 순서를 신경써야함. - dc App

[Gravekper(gravekper)]

밑에 내가 올린 영상에 있음

[익명(124.57)]

d[i][k] = i~N까지 k개를 사용해서 만들 수 있을 때 참 / 큰수라는 것은 당연히 앞자리가 가장 크면 됨 i를 a개를 켜가지고 수를 만들었을 때 그럼 d[i][k]가 참이 될려면 조건이 무엇일 까? d[i+1][k-a]가 참이어야 함. 왜냐면 i가 a개를 사용했으니 i+1 ~ N까지는 k에서 a개가 줄어든 값으로 만들어야 함으로 그럼 답은 d[0][K]가 참이면 -1이 아님. 근데 우리는 어떤 수 인가 까지 알아야 하므로 d[i][k]에 "i자리는 x이고 이때 a개를 사용했습니다" 라고 적어놓아서 이걸 역추적해가면됨 i번째가 가장큰 x를 가지도록 하고...

[익명(124.57)]

냅색 문제에서 어떤 물건을 집어넣었는지 역추적하는 방법과 비슷함

[글쓴이(211.202)]

답변 달아주신분들 모두 감사합니다!!