gomino   1년 전

각 쿠키를 오븐1에서 굽던지, 오븐2 에서 굽던지 선택지가 두개 뿐이라고 생각하여

다이나믹 배열을 dy[i][timea][timeb] = i번 쿠키부터 굽기 시작하고 오븐1에 넣은 시간 합이 timea, 오븐2에 넣은 시간 합이 timeb일때 최소시간

으로 잡으면 메모리를 잡을수가 없고,

그리디하게 해결할 수 있나 규칙을 생각해봐도 잘 떠오르지가 않습니다.

이 문제 관련해서 팁이나 힌트를 좀 얻을 수 있을까요?

hahaha   1년 전

저도 시간을 단위로 해서 접근했는데, 이런 식으로 정의했어요ㅎㅎ

d[i] = 오븐 1에서 i시간을 사용하지 않을 떄, 오븐2를 사용하는 최소시간

이렇게해서 dp 메모리를 최대 1000*100으로 잡을 수 있고,

오븐1에서 사용하는 시간과 오븐2에서 사용하는 시간 모두 알 수 있었어요.

gomino   1년 전

hahaha

오븐 1에서 i시간을 사용하지 않을 때 라는 말이

오븐 1 사용시간이 i 이내라는 것인가요?

hahaha   1년 전

제 설명이 부족했네요 ㅠㅠ

모든 쿠키를 오븐 1에서 굽는다고 가정했을 때,

sum = ∑ai 로 가정하고, 임의의 쿠키를 오븐1이 아닌 오븐2로 굽게 된다고 가정해서 d[i]를 세웠어요.

d[i]는 오븐 1에서 사용하지 않은 시간 i로 가정해서 d[i]에서 알 수 있는 것은

오븐 1에서 사용한 시간은 sum-i시간 오븐 2에서 사용한 시간은 d[i]시간으로 정의했습니다.

결국 쿠키를 굽는 시간 = min(오븐1에서 굽는 시간, 오븐2에서 굽는시간) = min(sum-i,d[i]) 로 찾았어요!




한편, d[i]=min(d[i], d[i-a[k]]+b[k] ) 로 생각했습니다!

hahaha   1년 전

min이 아닌 max로 수정합니다 !! 쿠키를 굽는 시간 = max(오븐1에서 굽는 시간, 오븐2에서 굽는시간) = max(sum-i,d[i])

gomino   1년 전

hahaha

친절하게 설명해주신 덕분에 해결하였습니다^^

정말 감사드립니다!!

댓글을 작성하려면 로그인해야 합니다.