목록백준 2156 (1)

시작이 반

[백준] 2156번(python 파이썬)

*연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 처음에는 계단오르기와 같은 방식으로 풀었지만 계단오르기는 1칸 뛰어서 올라갈수 있는데 이문제는 몇칸이든 뛰어서 시음을 할 수있다. 이는 n잔 주워졌을떄 n-1잔 뛰어서 시음을 할 수 있다. 때문에 배열을 n+1 x n 개 만들어서 풀었지만 메모리 초과가 나왔다. 메모리 제한이 128MB이다 입력 제한이 10000인데 10001 x 10000 개 만들어버리면 당연히 메모리 초과가 나온다. 다시 생각했을때 최대 2잔까지 건너뛰어서 마셔도 최대값을 구할수 있다고 생각했다. 6 1000 1000 1 1 1000 1000 이렇게 있을때 1, 2, 5, 6을 마시는게 최대값이다. 7 1000 1000 1 1 1 1000 1000 이렇게 있다면 1, 2, 4, 6,..
알고리즘/백준 2021. 2. 9. 15:50
이전 Prev 1 Next 다음