'''땅따먹기 게임을 하려고 합니다.
땅따먹기 게임의 땅(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로 돌렸다.
이게 최선의 코드는 아니나 효율성에서도 큰 문제 없이 돌아갔다.
'1일 1문제, 프로그래머스' 카테고리의 다른 글
| 간단한) 피보나치 수열 (0) | 2018.06.20 |
|---|---|
| 끝말잇기, 18년 섬머 문제? (0) | 2018.06.15 |
| 문자열 내림차순 배열.. (0) | 2018.06.12 |
| 두 정수가 주어졌을때 차이만큼 더한 값 구하기 (0) | 2018.06.08 |
| 레벨2, 가장 큰 정사각형 (0) | 2018.06.07 |
