목록땅따먹기 (1)

민규의 흔적

[Python 파이썬] 프로그래머스 - 땅따먹기

2024년 9월 10일문제 링크 : 프로그래머스 - 땅따먹기문제 접근 0번째 행부터 마지막 행까지 규칙에 맞춰 칸을 한 칸 씩 밟아가며, 최대로 많이 누적시킬 수 있는 점수를 출력하는 문제이다. 여기서 말한 규칙은 다음과 같다. 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 만약 1번째 열의 칸을 밟았다면, 다음 행에선 1번째 열 칸은 밟지 못한다는 의미이다. 마지막 행까지 도달하는 모든 경우의 수를 계산하기엔 최대 행의 개수가 100,000개로 시간복잡도가 엄청 불어나게 된다. 이를 효율적으로 풀기 위해 다이나믹 프로그래밍 기법을 활용하기로 결정하였다. DP(다이나믹 프로그래밍) 기법을 활용하고자 결정한 이유는 다음과 같다. 특정 칸 까지 누적할 수 있..
프로그래머스 2024. 9. 10. 19:58
이전 Prev 1 Next 다음