2579번-계단 오르기

문제)

연속된 3개의 계단을 밟지 않고 한 번에 한 계단, 또는 두 계단을 올라 마지막 도착 계단에 도달할 때, 얻을 수 있는 총 점수의 최댓값

 

해결 방법) DP , 작은 하위 문제로 큰 문제를 해결한다. 

 

DP 해결 방법

 

1. 테이블 정하기 

2. 점화식 구하기

3. 초기값 구하기

'''
1. 테이블 정의하기
d[i]=i번째 계단을 밟을때 얻는 최대값.
2. 점화식
d[i]=d[i-1]+c[i]
d[i]=d[i-2]+c[i]의 max

2. 초기값
d[0]=0
d[1]=c[1]
'''
n=int(input())
c=[0]
for i in range(n):
    x=int(input())
    c.append(x)
d=[0]*(n+1)
d[1]=c[1]
for i in range(2,n+1):
    d[i]=max(d[i-1],d[i-2])+c[i]
print(d[n])

처음엔 위와 같이 풀었다. 하지만 위의 풀이는 3개의 계단을 연속해서 밟지 않는다는 조건에 맞지 않는다. 

따라서 테이블을 다르게 설정해줘야 한다.

'''
1. 테이블 정의하기
D[i][j]=현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의
최댓값, 단 i번째 계단은 반드시 밟아야 함.j는 1이나 2.

2. 점화식 찾기
d[k][1]=max(d[k-2][1],d[k-2][2])+s[k]
d[k][2]=d[k-1][1]+s[k]

3. 초기값 설정
d[1][1]=s[1] d[1][2]=0
d[2][1]=s[2] d[2][2]=s[1]+s[2]
'''
s=[0]
n=int(input())
for i in range(n):
    x=int(input())
    s.append(x)
if n==1:
    print(s[1])
else:
    d=[[0]*3 for _ in range(n+1)]
    d[1][1]=s[1]
    d[1][2]=0
    d[2][1]=s[2]
    d[2][2]=s[1]+s[2]
    for i in range(3,n+1):
        d[i][1]=max(d[i-2][1],d[i-2][2])+s[i]
        d[i][2]=d[i-1][1]+s[i]
    print(max(d[n][1],d[n][2]))

- 다른 풀이 

1차원 배열로 해결하는 방법이 있다. 

'''
1. 테이블 정의하기
d[i]=i번째 계단까지 올라섰을 때 밟지 않을 계단의 합의 최솟값.

2. 점화식
d[i]=min(d[i-2],d[i-3])+s[k]

3. 초기값
d[1]=s[1] d[2]=s[2] d[3]=s[3]

최종값은 총 계단 합에서 min(d[i-1],d[i-2]) ㅐ주면된다. 
'''
n=int(input())
s=[0]
for i in range(n):
    x=int(input())
    s.append(x)
d=[0]*(n+1)
d[1]=s[1]
d[2]=s[2]
d[3]=s[3]

for i in range(4,n+1):
    d[i]=s[i]+min(d[i-2],d[i-3])
print(sum(s)-min(d[n-1],d[n-2]))

 

참고 : https://blog.encrypted.gg/974?category=773649 나의 알고리즘 스승님,,,갓킹독님💙