LADDER 문제 질문드려요~

  • 장홍준
    장홍준

    저는 DP로 풀었는데요.
    "D[i][j][Up/Left/Right] : i번째 행의 j번째 사다리 위치에서, 선이 이어지는 방향이 Up/Left/Right 중 하나에서 올 때, 그 위치에 이르기 위해서 필요한 사다리 줄의 최소 제거 횟수"라고 테이블을 정의하고 풀었습니다. 시간복잡도는 O(NM)이구요...
    해결하신 분들의 소스를 훑어보니 그리디하게 많이 푸셨던데..
    어떻게 푸셨는지 설명 부탁드려요~


    11년 전
3개의 댓글이 있습니다.
  • Being
    Being

    제가 몇 개 살펴 보니 다 DP인 것 같은데요 :-) 장홍준 님 방식과 비교해 차원을 하나로 줄였을 뿐인 것 같습니다.


    11년 전 link
  • 장홍준
    장홍준

    그렇군요 ㅠㅠ그럼 어떻게 차원을 줄인거죠?ㅠㅠ


    11년 전 link
  • Being
    Being


    사다리 줄을 고려하는 순서와 장홍준님의 계산 순서를 잘 고려해 보시면 위치만 저장해도 충분하다는 것을 알 수 있지요!


    11년 전 link

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