[Swift] 프로그래머스 - 땅따먹기

문제

땅따먹기 점수판 array가 주어짐

방향을 열 방향으로 한칸씩 내려가며 점수를 획득하여 점수 최댓값을 구하는 문제인데

같은 열 방향을 연속으로 밟을 수 없는 규칙이 있음

.+ 열의 갯수는 4개

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

풀이

• [시간초과] dfs로 풀어야 하지 않을까 란 생각을 했다. 범위가 크니깐..?

• [성공] dp로 도전.. (2차원 배열을 만들어서)

  dp[i] = dp[i-1]의 같은 열을 제외한 이전값들의 합 중 최댓값

  n-1번째 계산된 값을 중복적으로 계산할 경우가 생기기 때문이

  그럴 이유가 없으니깐 dp를 통해서 풀었어야 했음..

코드

처음 3중for문은 좀 아닌것 같아서

[1,2,3,4].map{$0}.filter{$0!=j}.forEach 문을 사용해서 풀었는데 시간초과가 떳다.

생각해보니 결국 j를 제외한 array을 만든다 해도 다시 for문을 돌려야 했기 때문에 O(n²)이 되기 때문에 for문으로 돌리는걸로 바꿧다 =_=