3개의 댓글이 있습니다.

• 
  Corea

  풀이를 서술하지 않고 설명하기가 힘들 것 같아, 아래 스포일러로 묶어둡니다.

  책에는 어떤 풀이가 쓰여있는지 지금 확인할 수가 없네요. 우선, 동적계획법의 배열 정의를 다음과 같이 할 수 있습니다.

  • D(i, j) = i번째 줄의 j번째 칸에 도달할 수 있으면 1, 없으면 0

  해당 문제의 경우에는 항상 '오른쪽' 혹은 '아래쪽'으로만 이동할 수 있기 때문에, 2중 for loop를 이용하여 D(i, j)를 채울 수 있습니다. 이 때 두 가지 방법이 있습니다.

  1. D(i, j)를 채우기 위해 D(i-1, j), D(i-2, j), ... 와 D(i, j-1), D(i, j-2), ... 를 모두 확인하는 방법입니다. 이 경우 이전 칸의 숫자를 확인하여 (i, j)로 도달 할 수 있는지를 확인해야겠죠.
  2. D(i, j)에서 그 다음칸을 채우는 방법입니다. (i, j)칸의 숫자를 A라 하면, 만약 D(i, j)가 1인 경우 D(i+A, j)와 D(i, j+A)를 1로 만들어 줄 수 있겠죠.

  
  7년 전 link

• 
  Corea

  만약 해당 문제를 해결하셨다면, 다른 사람의 코드를 통계 페이지에서 확인하실 수 있습니다. 다른 분들 중 반복적 방법으로 해결하신 분들도 많으니, 읽어보시면 도움이 될 것 같네요.

  
  7년 전 link

• 
  Jaekwan

  답변 감사합니다.
  배열에 대한 정의를 만드는 부분이 중요하군요. 정의를 만든 후 여러가지 방법으로 풀 수 있다는 부분에 큰 수 배우고 갑니다. 감사합니다.!

  
  7년 전 link

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