[백준] 2579 계단오르기

1. 문제

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

2. 풀이

정말 정말 오랜 숙원을 풀었다 ㅋㅋㅋㅋㅋ

하 보니까 2년전에도 못풀었던데

DP는 진짜 나한테 어려웠는데 눈앞에 닥친 코테때문에 겁나 열심히 하는중 <- 안나오면 눈물,,까진 아니고 알아서 좋지뭐

 

틀렸습니다 -> 메모리 초과 -> 맞았습니다!!! 의 여정입니다.

1) 먼저, 저는 솔직히 다른 방법이 크게 생각이 안나서 고민을 많이한게
[1] 배낭문제처럼 테이블로 풀기
[2] 한 리스트에 계속 max 값 업데이트하는 방식
이정도로 고민했는데,, 결론적으로 보면 2번 방식에 근접하게 풀이한거 같긴함

2) 무조건 처음을 첫 번째나 두번째에서 시작해야하기 때문에 저는 메모리를 최소한으로 하려고
dp = [] 를 선언한 뒤에, [(첫 번째 계단 값, 연속횟수=1)], [(두 번째 계단 값, 연속횟수=1)] 로 이중리스트를 생성했습니다.

2)번 설명

 

3) 이제 여기서 첫 번째 리스트 값을 pop(1) 합니다. 이를 한 칸 뛰기 / 두 칸 뛰기를 해서 다음 리스트를 다음 계단의 상태라 생각하고 넘겨줍니다. 한 칸 뛰면 지금 pop한 상태니 dp[0] 리스트에 추가해야하고, 두 칸 뛴건 dp[1] 리스트에 추가해줘야 합니다. 이 pop한 좌표는 한 개 이상일 수 있기 때문에 for문을 씁니다.

3)번 설명

4) 근데 여기서 메모리 초과가 일어나지 않으려면 새로운 것을 추가해야 합니다. 왜냐? 그렇지 않으면 리스트 안에 엄청나게 많은 값이 들어가서 128MB 조건을 넘습니다. 그래서 원래는 아래처럼 나왔습니다. 숫자가 적어서 그렇지 300개 계단 들어가면 끝도 없이 많아지긴 하겠네요.. 그렇기 때문에!!! 저는 생각을 해봤습니다.

많은 출력 ,,

4-1) 바로 뒤의 연속횟수 상태가 같은 숫자 중 MAX 값만 남기는 것입니다. 어차피 연속상태가 같으면 그 뒤에 이동에는 차이가 없기 때문에 앞에서 100번을 왓던 50번을 왓던 상관이 없어집니다. 그래서 MAX 값만 남기는 작업을 취해줘야합니다.

 

이렇게 하면 메모리 문제도 해결하면서 이 문제를 해결할 수 있습니당!!!! 굿

 

## code ##

import sys

n = int(sys.stdin.readline())
stairs = []
max_series = []

for _ in range(n):
    stairs.append(int(sys.stdin.readline()))

def dynamic(dp, idx):
    # 최종 인덱스에 다다르면 끝
    if idx == len(stairs): return

    # 메모리 절약으로 매번 리스트에서 빼주면서 다/다다음칸으로 이동할 친구들 추출
    data = dp.pop(0)
    # 다다음칸 추가
    dp.append([])

    for d in data:
        # 연속 2번째인 경우 pass
        if d[1] < 2:
            dp[0].append((stairs[idx] + d[0], d[1]+1))

        # 2칸 뛰어야 하는데 1개 남아도 pass
        if idx < len(stairs) - 1:
            dp[1].append((stairs[idx + 1] + d[0], 1))

    # 메모리 감축용
    zero_list, one_list = [], []
    for item in dp[0]:
        if item[1] == 1:
            zero_list.append(item)
        else:
            one_list.append(item)
    dp[0] = [max(zero_list, key=lambda x: x[0]), max(one_list, key=lambda x: x[0])]
    dynamic(dp, idx+1)

if n == 1:
    print(stairs[0])
else:
    # 시작이 무조건 첫번째/두번째라서 지정해놓고 dp 시작
    dp = []
    dp.append([(stairs[0], 1)])
    dp.append([(stairs[1], 1)])

    dynamic(dp, 1)
    print(max(map(max, dp[0])))