10개의 댓글이 있습니다.

• 
  Being

  식 적기 귀찮아서 대충 정리하면 D = 0이면 모든 Earliness 텀은 0이 되고 AD 텀도 0이고 Tardiness 텀만 문제가 되는데요, D가 늘어나면 A > B라서 AD 텀이 늘어나는정도가 Tardiness 텀이 늘어나는 정도보다 빠르고 Earliness 텀도 늘어나기만 합니다. 이건 이 문제에서 가장 간단한 부분인 것 같은데요..

  
  11년 전 link

• 
  Being

  또 우리가 Tardiness 텀이랑 Earliness 텀을 작업이 끝나는 시간 기준으로 정의했기 때문에, 최적의 데드라인이 작업이 끝나는 시간이 아니라 중간이라 가정하면 앞이나 뒤로 조정하면 항상 같거나 더 좋게 만들 수 있습니다.

  
  11년 전 link

• 
  Being

  인덱스가 A, B, C, N으로만 정해지는 건 다른 좀 더 간단한 문제를 먼저 해결해 보시면 좋을 것 같습니다. 1차원 수직선 상에 N개의 점이 있을 때, 어떤 점 P가 모든 점들과의 거리의 합을 최소화하려면 어디에 위치해 있어야 하나요? :) 일단 지금은 여기까지만 말씀드리는게 좋을 것 같네요.

  
  11년 전 link

• 
  yeonzzg

  정리해보니 말씀대로 A>=B일땐 D=0이 수식이 항상 최소가 되네요..
  아직 A B C N가지고 인덱스가 정해진다 라는 부분이 잘 이해가 안가는데요, D의 인덱스가 정해진다는게 정확히 몇번째 작업에서 끝나는지 인지 아니면 정확한 시간을 말하는건지 잘 모르겠네요 ㅠㅠ
  두가지 다 수식으로 보면 앞 뒤로 어떤 종류들의 Ti들이 있는지에 따라 완전 달라질거같아요..ㅠ 분명 어느 시점에서는 앞뒤로 조정을 해서 무조건 최적이 되는 시점을 일이 끝나는 시점으로 조정이 가능은 한데, A B C N만 가지고 인덱스를 구한다 라는 점이 생각해봐도 너무 어렵네요 ㅠ

  
  11년 전 link

• 
  Being

  몇번째 작업에서 끝나는지를 정할 수 있다는 겁니다. 제가 말씀드린 간단한 문제는 해결해 보셨는지요?

  
  11년 전 link

• 
  yeonzzg

  뭔가 감을 잡은거같아서 파워 제출해봣는데 소용이 없네요..ㅠ 말씀하신 부분은 점마다 가중치가 없다면 항상 가운데 점이 최선이 되는 예제로 알고있어요.. A B C N 가지고 몇번째인지를 좌 우 개수 c1 c2와 A B C N으로 조절해나가면서 구해봤는데 맞는지 모르겠네요.. 그리고 몇번째를 안 후에가 또 중요하네요 ㅠ.ㅠ 이 부분을 n^2 dp 혹은 그리디하게 해결 가능한 것이겠지요..? dp로 하자니 n^3밖에 안떠오르네요 ㅠ.ㅠ

  
  11년 전 link

• 
  yeonzzg

  와.........해결했네요 ㅠㅠㅠ 정말 감사드립니다 ㅠㅠ dot product 얘기가 그런 말이었네요 휴 ㅜㅜ

  
  11년 전 link

• 
  yeonzzg

  n^2 dp로는 어떻게 테이블을 잡았을까요? 궁금하네요..?.?

  
  11년 전 link

• 
  Being

  축하드려요~

  
  11년 전 link

• 
  yeonzzg

  정말 감사드립니다 ㅎㅎ 매번 좋은 가르침 감사드려요

  
  11년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.