Hoguz

'''땅따먹기 게임을 하려고 합니다. 

땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 

모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 

각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 

같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.'''

# 땅따먹기 역시 동적 프로그래밍으로 풀었따.

내 힘으로 풀어서 너무 기분이 좋구나.. 좀 시행착오도 많긴했따.

문제는 이러하다

[[1,2,3,5],

[5,6,7,8],

[4,3,2,1]];

위와 같은 배열이 있을 때 열이 중복 안되게 하여 최대 값을 구하는 것이다.

이런 경우 5 + 7 + 4 = 16이 제일 큰 경우가 된다.

위에서 언급 했듯이 이는 다익스트라 알고리즘과 매우 유사하다.(최소냐 최대냐의 차이일뿐)

최대값을 비교하고 이를 업데이트 하는 동적프로그래밍 개념을 다시금 사용하였다.

처음에 이 문제를 접근하려 했을때는 동적프로그래밍을 염두 했음에도 불구하고 row, column을 제어하려고 노력하였다.

그리고 가장 잘못 생각했떤게, 한번에 max를 찾으려고 했다는 것이다.

무슨 의미냐면 1부터 시작할 경우, 6,7,8에 1을 더한 값을 구한 후 바로 3,2,1 에 이를 계산 하려고 했다.

모든 경우의 수를 다 생각을 해서 해야했기에 이는 최소 O(N^3) 의 시간 복잡도가 필요했을것이다

하지만 다익스트라를 보면

다익스트라는 한번에 마지막 노드까지 전진하지 않는다. 시작 노드에서 다음노드로, 또 해당노드의 값을 계산 하고 이를 업데이트 하고 넘어간다. 

그렇기에 이 문제에서도 1번으로 6,7,8을 계산 한 후, 2번으로 다시 계산하고 값을 비교하고 업데이트 하는 식으로 하면 된다.

로직은 다음과 같다.

1. 처음 시작은 0번 로우의 원소들이다.

2. 2번 로우의 원소들과 비교한다

- 여기서 비교는 1번)(오리지널 원소)와 2번)(시작 노드 + 오리지날 원소 값)을 비교해서 1번)이 작으면 그 값을 2번으로 바꿔준다.

- 비교해야하는 주체가 필요하므로 나는 복제 테이블을 하나 만들어서 오리지널 원소는 복제테이블에서 뽑아오고 업데이트는 다른 리스트를 해주었다.

3. 반복.

1번에서 시작하면

[[1,2,3,5],

[5,6,7,8],

   7,8,9 가 되고 모두 오리지널 보다 크므로 값이 바뀐다. 

[4,3,2,1]];

바뀐후

[[1,2,3,5],

[5,7,8,9],

[4,3,2,1]];

이제 2번에서 시작한다.

[[1,2,3,5],

[5,7,8,9],

7,   9, 10 2번 + 2번째 원소들의 합이 오리지널보다 더 크다. 업데이트 하자.

[4,3,2,1]];

[[1,2,3,5],

[7,7,9,10], 7은 2번과 같은 인덱스이므로 문제의 규칙에 따라서 적용되지 않았다.

[4,3,2,1]];

다음은 3번이다.

[[1,2,3,5],

[7,7,9,10],

8, 9,  , 11 역시 모두 큰 값이므로 업데이트 해준다

[4,3,2,1]];

이렇게 반복을 하면 된다.

코드 상에서 row를 움직이기 위해 변수를 하나 선정한후 while로 돌렸다.

이게 최선의 코드는 아니나 효율성에서도 큰 문제 없이 돌아갔다.