반응형
https://programmers.co.kr/learn/courses/30/lessons/12913
코딩테스트 연습 - 땅따먹기 | 프로그래머스
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면
programmers.co.kr
DP문제.
table[row][index] 위치가 row, index위치까지 도달했을 때 얻을 수 있는 최댓값이라고 정의한다면,
이 값은 land[row][index] + max(table[row-1][0~4까지의 값 중 index를 제외한 나머지]) 가 된다.
만약 row가 1이고 index가 2라면
table[1][2] = land[1][2] + max(table[0][0], table[0][1], table[0][3])이 되는 것.
table을 따로 생성할 수도 있지만,
land[row][index] = land[row][index] + max(land[row-1][range(4) - {index}] 그대로 연산해도 무방하다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 도둑질 (Level 4) (0) | 2020.01.22 |
|---|---|
| [Python] 프로그래머스. 스티커 모으기(2) (Level 4) (0) | 2020.01.18 |
| [Python] 백준 2667. 단지번호붙이기 (0) | 2020.01.15 |
| [Python] 백준 5397. 키로거 (0) | 2020.01.13 |
| [Python] 프로그래머스. 입국 심사 (Level 3) (0) | 2020.01.11 |