수다닷컴

질문 제목 : 이런 문제.. 알고리즘을 어떻게 짜야할까요??dp(다이나믹프로그래밍) 으로 이 문제를 해결해야하는데.. 어떻게 해야하는건지;;질문 내용 : 아래의 문제를 어떻게 구현해야할까요??

문제는 너무 길구요.. 대략 어떻게 구현하라는 정보가 있길래 이거를 보여드릴테니 실제 c언어 상에선 어떻게 코딩을 해야하는건지 알려주세요.. ㅜ

ee[m,m,1] = ee[m,m,2] = 0
ee[i,i,1] = ee[i,i,2] = 무한대 if i != m
dd[i,i,1] = dd[i,i,2] = pp[i,i,1] = pp[i,i,2] = 0
d[1~n] 과 w[1~n] 그리고 n, m은 input으로 들어오기에 이미 값이 들어있음..

최종 목표 : min { ee[1,n,1], ee[1,n,2]}

ee[l,r,1] = min {ee[l+1,r,1] + (dd[l+1,r,1] + d[l+1] - d[l]) * w[l],
ee[l+1,r,2] + (dd[l+1,r,2] + d[r] - d[l]) * w[l]}

ee[l,r,2] = min {ee[l,r-1,1] + (dd[l,r-1,1] + d[r] - d[l]) * w[l],
ee[l,r-1,2] + (dd[l,r-12] + d[r] - d[r-1* w[l]}

dd[l,r,1] = (dd[l+1,r,1] + d[l+1] - d[l]) 만약 ee에서 min이 앞에 것일 경우적용
(dd[l+1,r,2 + d[r]- d[l])만약 ee에서 min이 뒤에 것일 경우 적용

dd[l,r,2]= (dd[l,r-1,1] + d[r] - d[l]) 만약 ee에서 min이 앞에 것일 경우적용 (dd[l,r-1,2] + d[r] - d[r-1]) 만약 ee에서 min이 뒤에 것일 경우적용pp[l,r,1] = l+1 만약 ee에서 min이 앞에 것일 경우적용 r 만약 ee에서 min이 뒤에 것일 경우적용pp[l,r,2] =l 만약 ee에서 min이 앞에 것일 경우적용 r-1 만약 ee에서 min이 뒤에 것일 경우적용위와 같은데요..위에서 배열의 제일 끝에 달린 1과 2는 아마.. 배열을 따로 ee1 ee2 이런식으로 나눠야하는거 같네요..문제는.. 위와 같은 힌트를 가지고 구현을 해야하는데.. 어떤 형식으로 짜야 dp 알고리즘으로 최종목표인 min { ee[1,n,1], ee[1,n,2]} 를 구할 수 있을까요?? 제가 이거 지금 계속 붙잡고 있는데도 도저히 모르겠거든요 ㅜ코딩을 짜달라는건 아니구요.. 대충 어떻게 구현을 해야하는지 방향만 잡아주시면 감사하겠습니다 (__)

신청하기