hopscotch

땅따먹기

• 문제

• 간단한 문제 설명
  100이하의 자연수로 채워진 N행 4열의 2차원 배열이 주어질 때, 첫 번째 행부터 마지막 행까지 각 행에서 하나의 요소만을 합하면서 이동할 때 얻을 수 있는 최대 정수를 반환하는 문제. 단, 다음 행으로 이동할 때 같은 열로 이동할 수 없다.

• 내 코드

• 내 코드 설명
  각 요소로 올 수 있는 경로 중 문제의 조건에 만족하는 경로를 기억하며 해결하는 문제이다.
  예를 들어 a행 b열에 올 수 있는 이전 요소는 a-1행에서 b열을 제외한 요소들 중 최댓값을 가진 요소이다. 주어진 2차원 배열의 두 번째 행부터 마지막 행까지 각 요소에 이전 행에서 올 수 있는 최댓값을 더해간다. 이렇게 마지막 행까지 연산을 하고 마지막 행에서 최댓값을 반환한다.
  문제 해설 강의

  처음 문제를 보고 세운 전략은 두 번째 행부터 마지막 행까지 각 요소로 올 수 있는 이전 요소들 중 최댓값을 더해가면서 값을 구하는 전략을 세웠다. 정확성 테스트부터 시간초과가 나와서 다른 방법을 찾다가 해설 강의를 보고 다이나믹 프로그래밍으로 전략을 세우는 방법을 알게되었다.