[python/2579]계단 오르기

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

2579번: 계단 오르기

 

문제 풀이를 보시려면 더보기를 클릭하시면 됩니다.

계단 오르기

계단을 오르는 규칙에 유의하면서 점화식을 만들어 주면 됩니다.

규칙

1. 계단은 1 칸이나 2 칸만 오를 수 있다.

2. 연속된 3 개의 계단을 밟으면 안 된다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

 

맨 마지막 도착 계단을 밟으면서 연속된 3 개의 계단을 밟지 않으려면 2가지의 경우의 수가 발생합니다.

n-1과 n을 밟을 경우

값 = n-3의 값 + n-1의 값 + n의 값

n-2와 n을 밟을 경우

값 = n-3의 값 + n-2의 값 + n의 값

이 2가지 경우 중 큰 값을 출력하면 됩니다.

 

한 가지 주의할 점은 계단이 3칸 미만일 경우 예외처리를 해주어야 합니다.

 

전체 코드

def solve(list):
    # answer라는 리스트 생성
    answer = [0 for _ in range(len(list))]
    # 0-2까지 인덱스에 미리 초기값을 설정
    answer[0] = list[0]
    
    # list 길이가 2보다 작을 경우는 answer[0]값을 리턴
    if len(list) < 2:
        return answer[0]
    
    answer[1] = list[0] + list[1]
    
    # list 길이가 3보다 작을 경우는 answer[1]값을 리턴
    if len(list) < 3:
        return answer[1]
    
    answer[2] = max(list[1] + list[2], list[0] + list[2])
    # 3부터 나머지 길이 만큼 반복
    for i in range(3, len(list)):
        # 2가지 경우의 수중 큰 수를 answer 리스트에 저장
        answer[i] = max(answer[i - 3] + list[i - 1] + list[i], answer[i - 2] + list[i])
    # 맨 마지막 값 외에는 문제 풀이를 위한 값이므로 마지막 값 리턴
    return answer[-1]
 
if __name__=='__main__':
    input_list = []
    # 입력 받기
    for i in range(int(input())):
        input_list.append(int(input()))
 
    answer = solve(input_list)
    # 출력
    print(answer)