코딩테스트

[BaekJoon 2579번] 계단오르기 문제(Python)

하루살이 2022. 1. 10. 01:49

코딩테스트 연습 3일차

 

계단오르기 문제입니다.

 

문제링크: https://www.acmicpc.net/problem/2579

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

 

Solution

import sys

input = sys.stdin.readline

n = int(input()) #계단의 개수

score = []
sum = []

for _ in range(n): #점수 넣기
    score.append(int(input()))

if n==1:
    print(score[0])

elif n == 2:
    print(max(score[0]+score[1], score[1]))

else:
    sum.append(score[0])
    sum.append(max(score[0] + score[1], score[1]))
    sum.append(max(score[0] + score[2], score[1] + score[2]))

    for i in range(3, n):
        sum.append(max(sum[i-3] + score[i-1] + score[i], sum[i-2] + score[i]))

    print(sum[-1])

또는

 

import sys

input = sys.stdin.readline

n = int(input()) #계단의 개수

score = []
sum = []

for _ in range(n): #점수 넣기
    score.append(int(input()))

if n==1:
    print(score[0])
    exit()
elif n == 2:
    print(max(score[0]+score[1], score[1]))
    exit()

sum.append(score[0])
sum.append(max(score[0] + score[1], score[1]))
sum.append(max(score[0] + score[2], score[1] + score[2]))

for i in range(3, n):
    sum.append(max(sum[i-3] + score[i-1] + score[i], sum[i-2] + score[i]))

print(sum[-1])

풀이

마지막 계단 전 계단을 포함하느냐, 안하느냐에 따라 나누기