# 땅따먹기 문제

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

/* 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다. 제한사항 행의 개수 N : 100,000 이하의 자연수 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다. 점수 : 100 이하의 자연수 */ int solution(vector<vector<int> > land) { int answer = 0; int max = 0; for (int i = 1; i < land.size(); i++){ for (int j = 0; j < 4; j++, max = 0){ for (int k = 0; k < 4; k++){ if (j != k) { max = (max > land[i - 1][k]) ? max : land[i - 1][k]; } } land[i][j] += max; } } max = 0; for (int i = 0; i < 4; i++){ max = (max > land[land.size() - 1][i]) ? max : land[land.size() - 1][i]; } answer = max; return answer; }

선택한 숫자와 같은 열은 다음 행에서 선택할 수 없다는게 핵심이다.

어쨋든 경우의 수를 전부 검사를 해야한다. 그렇다면 계산하는 과정에서 재사용할 수 있는게 있을까?

이렇게 생각해보자.

1번 행에 (1, 2, 3, 5)가 있고 2번 행에 (5, 6, 7, 8)이 있다고 가정하자.

1번 행에서 어떤 숫자를 선택했다면 2번 행에서는 어느 숫자를 골라야 가장 큰수가 될까?

예를들어 1번 행에서 1을 선택했다면, 우선 같은 열에있는 숫자는 다음 행에서는 고를 수 없다.

그럼, 2번 행에서는 5를 제외한 나머지를 고를 수 있다.

2번 행에 있는 5라는 숫자 기준에서 생각해보자.

2번 행에 있는 5라는 숫자는 1번행에서 어떤 숫자를 골라야 가장 큰 값이 될까?

바로 1번 행에 숫자 5이다. ( 그리고 같은 열[=column]이 아니다. )

그렇다는 건, 어떤 선택을 하건 2번 행에 있는 숫자5에 관점에서는 1번 행에 있는 5라는 숫자를 골라야 높은 값을 유지할 수 있다.

이거를 좀더 보기 좋게 바꾸어보면..

1번 행 (1, 2, 3, 5)

2번 행 (10, 6, 7, 8)

2번 행의 첫째자리에 존재하던 숫자5에 1번 행의 가장 큰 숫자인 5를 더해줬다.

이런식으로 작업을 진행하면.

2번 행 (10, 11, 12, 11) 이 완성된다.

즉, 2번 행에 있는 각 숫자들의 관점을 기준으로 자신들이 가장 큰 값이 되는 경우를 계산해서 해당 위치에 대입시킨 결과다.

이런 방식을 이용하면, N행에 대해서 각 행에 포함된 각각의 숫자들이 가질 수 있는 최고값을 알 수 있다. 그리고 이는 각 행의

공간에 계산되어서 저장되기 때문에 다시 사용할 수 있다.