sgc109   8년 전

약간 복잡하고 지저분한것같긴하지만


상점들을 방문할때는 왼쪽에있는 상점을 방문하거나 오른쪽을 방문하거나 두가지 경우가있고

가까이에 있는 상점을 무조건 먼저 만나게된다는것 그리고

상점을 방문할수 있는 방법이 출발점을 기준으로

왼쪽에있는 상점->더 왼쪽에있는 상점으로

왼쪽->오른쪽

오른쪽->왼쪽

오른쪽->오른쪽

이렇게 추가적으로 발생하는 시간을 계산하는 경우의수가 네가지가 있다는것에 착안해


DP(i,j,k) = 출발점을 기준으로 왼쪽에 i개 오른쪽에 j 개를 방문한직후 출발점을기준으로 왼쪽또는 오른쪽에있을때 대기시간들의 합의최소값과 마지막 상점에 방문할때까지 걸린시간(pair형태로) (k가 0이면 출발점보다 왼쪽 1이면 오른쪽에 있다는뜻)

로 잡고

D(i,j,0)는 D(i-1,j,0)과 D(i-1,j,1) 를 보고 직전상점에서 다음상점까지의 거리를 각각 더해서 대기시간의 합이 더 작은값을넣고(만약 같다면 지금방문하는 도시까지 걸리는 시간이 적은쪽을 D(i,j,0) 에넣음

D(i,j,1)는 D(i,j-1,0)과 D(i,j-1,1) 를 보고 위와 같은 식으로 계산해서

left,right 가 시작점을 기준으로 왼쪽에있는 방문할 상점의 수와 오른쪽에있는 방문해야할 상점의수일때

최종적으로 D(left,right,0) 과 D(left,right,1) 각각의 대기시간의 합의 최소값을 출력하도록해서


문제에있는 예제와 제가 간단하게 만들어본 예제들은 모두 올바른 값이 출력됐는데

어떤부분에서 잘못된건지 잘모르겠습니다.

사실 코드를 작성하고도 뭔가 시원한기분이 안들고 복잡해서 완벽하게 이해하지못한 느낌이긴했는데

제 설명이 좀 뒤죽박죽이긴하지만 이게 아예잘못된 방법인지 가능성이있는 방법인지궁금합니다.


shjgkwo   8년 전

풀이 방법은 맞으신데.. 뭐가 틀렸는지 못찾겠어요 ㅠㅠ

일단 생각해볼 수 있는 실수가, 0이나 1을 바꾸어 쓰셨다던가. tmp1과 tmp2를 바꾸어 썻다거나.. 이런 경우일텐데 찾기가 보통 어려운게 아니네요..

왼쪽의 x개 오른쪽의 y개로 하시지 말고 x번 지점 부터 y번 지점까지 방문했고 (x <= y) 0이면 왼쪽 1이면 오른쪽

이런식으로 하면 좀 더 소스짜기 수월하실 거에요.


밑에는 제 소스인데 x번 지점부터 y번 지점까지 방문했고 왼쪽에 있음을 dp(x, y, 0)로 나타내었습니다.(오른쪽은 1)

이렇게 하면 네가지 경우만 생각하면 되죠

(x, y, 1) => (x-1, y, 0) or (x, y+1, 1)

(x, y, 0) => (x-1, y, 0) or (x, y+1, 1)

sgc109   8년 전

@shjgkwo 아.. x 부터 y 까지 방문 으로보면되는군요.. 감사합니다 ㅎㅎ

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