개인공부-2
- 문제 설명
-> 땅따먹기 게임 진행
-> 2차원 배열로 주어지며, 전 행에서 밟은 열은 밟지 못함
-> 이 때 구할 수 있는 최대 값
- 초기 접근
-> 단순하게 처음 최대값을 시작으로 전과 같은 열을 밟지 않는 조건을 넣고 sum을 구했을 때
테스트 1번은 통과했지만, 나머지는 전부 통과하지 못했다.
- 반례
-> 처음에 최대값으로 시작하지 않더라도 총 합이 더 클 수 있기 때문에 열 마다의 최선의 경우의 수를 전부 구해야함.
land[i][0]+= Math.max(land[i-1][1],Math.max(land[i-1][2],land[i-1][3]));
land[i][1]+= Math.max(land[i-1][0],Math.max(land[i-1][2],land[i-1][3]));
land[i][2]+= Math.max(land[i-1][0],Math.max(land[i-1][1],land[i-1][3]));
land[i][3]+= Math.max(land[i-1][0],Math.max(land[i-1][1],land[i-1][2]));
- 선택한 열에서 같은 열이 아닌 최선의 선택의 경우의 수를 모두 구하는데, 그 때의 합을 구해 최대값을 구한다.