Programmers
Meet the best programming lessons in videos and practices. Programmers provide programing lessons, algorithm problems, programming competitions, and blockchain materials.
프로그래머스 문제풀이
문제
코딩테스트 연습 – 땅따먹기
Suppose that you are going to play a hopscotch game. In the hopscotch game, the land consists of “N” rows and 4 columns where the score is written on each space. As you are moving down the rows one by one, stepping on the spaces, you should only touch 1 space among the 4 spaces in the row. However,…
문제설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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 이하의 자연수
입출력 예
| land | answer |
|---|---|
| [[1,2,3,5],[5,6,7,8],[4,3,2,1]] | 16 |
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
문제해석과정
- 한 행씩 내려가면서 값 하나를 뽑아서 더한다.
- 한 행씩 내려올때 같은 열의 값을 더할 수 없다.
- 마지막행까지 내려왔을때, 최고점을 구한다.
위 같은 문제 및 제한사항을 해석하고 문제풀이를 시작하면 됩니다.
나의 풀이
이번 문제는 현재 행에 전 행의 다른 열 값 중 최대값을 더하면서 내려가면 되는 문제입니다.
def solution(land):
for a in range(1,len(land)): #행만큼 반복
for b in range(4): #열만큼 반복
land[a][b] = land[a][b] + max(land[a-1][:b]+land[a-1][b+1:]) #현재 행의 값에 전 행의 다른 열 값 중 최대값을 더함
return max(land[-1]) #마지막 행의 최대값을 출력
다른 사람의 풀이
다른 풀이도 저와 비슷해서 별도로 들고오지는 않았습니다.
관련 링크
문제해결과정에서 기초가 부족하다고 느껴지시면 아래 정리 글을 참고해주세요.
추가적으로 궁금한 사항이나 글에 대한 개선점 알려주시면 피드백 적극 반영하도록 하겠습니다.
Python 문법 총 정리1 – Zzrany Blog
여기는 Python을 공부하며 학습한 내용을 정리하는 블로그입니다. 해당 포스팅에서는 개발시 참고하실 수 있도록 Python 문법들을 한눈에 보이도록 필요한 내용만 간략하게 정리해보았습니다.
Python 문법 총 정리2 – Zzrany Blog
여기는 Python을 공부하며 학습한 내용을 정리하는 블로그입니다. 해당 포스팅에서는 개발시 참고하실 수 있도록 Python 문법들을 한눈에 보이도록 필요한 내용만 간략하게 정리해보았습니다.