백준 2579_계단 오르기 / Python

문제

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

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력 1 

6
10
20
15
25
10
20

예제 출력 1

75

---

알고보니 이 문제는 5달 전에 풀다가 포기했던 문제..

결국 못풀었었음.

마지막에 시간초과된 저 코드는 

import sys
from itertools import product
n=int(sys.stdin.readline().rstrip())
stairs=[]
for _ in range(n):
  stairs.append(int(sys.stdin.readline().rstrip()))

cs=[]
for i in range((n+1)//2): 
  a=[]
  for _ in range(i):
    a.append(2)
  for _ in range(n-2*i):
    a.append(1)
  cs.append(a)
if n>=3:
  cs=cs[1:]

def perm(a):    
    length=len(a)     
    if length==1:   
        return [a]
    else:
        result=[]     
        for i in a:     
            b=a.copy()    
            b.remove(i)   
            b.sort()    
            for j in perm(b):    
                j.insert(0, i)    
                if j not in result:     
                    result.append(j)     
    return(result)

cs2=[]
for cs_case in cs:
  res=perm(cs_case)
  for i in res:
    cs2.append(i)

#연속 2개인지 검사
def remove_consecutive_ones(cs2):
    i = 0
    while i < len(cs2):
        count = 0
        for j in range(1,len(cs2[i])):
            if cs2[i][j] == 1:
                count += 1
                if count == 2:
                    cs2.pop(i)  
                    break
            else:
                count = 0  
        else:
            i += 1 

remove_consecutive_ones(cs2)

pnts=[]
for cases in cs2:
  pnt=0
  a=0
  for num in cases:
    a+=num
    pnt+=stairs[a-1]
  pnts.append(pnt)
print(max(pnts))

코드 짱길고... 뭐가 뭔지 하나도 모르겠고 참... 읽고싶은 마음이 안드는 코드이다..

 

하여튼 오늘 다시 쓴 코드는

import sys
n=int(sys.stdin.readline())
lst=[]
for _ in range(n):
  lst.append(int(sys.stdin.readline()))

def stairs(lst,cur, n, cont):
  #cur: 현재 위치  n: 계단 총 갯수
  #cont: 연속으로 몇번 올랐는지. 0,1가능. 2이면 무조건 다다음꺼 밟아야함.
  if cur==n:  #계단이 끝날 때
    return 0
  next, n_next=lst[0],lst[0]	#초기값
  if cont<2:   #바로 다음꺼 밟기
    cont+=1	#연속+1
    next=lst[cur]+stairs(lst,cur+1,n,cont)
  
  if cont==2 and cur<n-2:  #다다음꺼 밟기
    cont=0	#연속 0으로 초기화
    n_next=lst[cur]+stairs(lst,cur+2,n ,cont)

  return max(next,n_next)

print(stairs(lst,0,n,0))

짧은 시간동안 재귀코드에 나름 익숙해졌을지도..

근데 여전히 시간은 초과..~

Memoization까지 써야하나보다.

 

#메모이제이션 추가
import sys
m = int(sys.stdin.readline())
lst=[0] #시작점을 0인 계단으로 인식.
for _ in range(m):
  lst.append(int(sys.stdin.readline()))

memo = {}

def stairs(lst, cur, n, cont):
  #cur: 현재 위치  n: 계단 총 갯수
  #cont: 연속으로 몇번 올랐는지. 1이면 무조건 다다음꺼 밟아야함.

  #마지막 계단
  if cur == n:    
    return 0

  #마지막 전 계단
  if cur == n-1:  
    #연속 3개 불가 조건에 걸리지 않고 마지막꺼 밟음.
    if cont < 1:  
      return lst[cur+1] + stairs(lst, cur+1, n, cont+1)  
    #마지막꺼 밟았을 때 연속 3개 되면 안됨. 그 경우 최솟값 처리.
    else:       
      return -30000000

  #Memoization. 중복계산 방지
  if (cur, cont) in memo:
    return memo[(cur, cont)]

  next, n_next = lst[0], lst[0]	#초기값, 시작점

  #이미 연속 2개이면 무조건 다다음꺼 밟기
  if cont == 1:  
    n_next = lst[cur+2] + stairs(lst, cur+2, n, 0)  #다다음꺼 밟았으니 연속 0으로 초기화
    return n_next

  #연속이 <1인 경우 다음꺼/다다음꺼 모두 가능
  next = lst[cur+1] + stairs(lst, cur+1, n, cont+1) #연속변수+1
  n_next = lst[cur+2] + stairs(lst, cur+2, n, 0)  #연속 0으로 초기화

  res=max(next,n_next)
  memo[(cur, cont)]=res

  return res

print(stairs(lst, 0, m, -1))
#cont변수 초기값을 -1로 주는 이유는 연속 3개 불가능 조건에 시작점은 포함되지 않기 때문.

메모이제이션 뿐만 아니라 다른 부분도 오류가 있어 고쳐주었다.

조건 처리 해주어야하는 부분은 하늘색, 핑크색, 연두색 부분

1. 마지막 계단일 때.

2. 계단을 이미 연속 두번 올랐을 때 -> 무조건 2칸 뒤 계단.

3. 마지막 칸은 필수. 하지만 이미 연속 두 번 올랐을 때 -> 이 경우는 아예 고려하면 안되므로 최솟값 처리.

 

---

스터디에서 처음 받은 배열을 거꾸로 뒤집어 생각하면 첫 계단은 무조건 밟게끔 하면 된다는 걸 알아서 그 방식대로 풀어보려고 했는데 어디가 문제인지 도저히 모르겠다.

.

.

라고 쓰고나니 갑자기 어디가 문젠지 보여서 풀었다..어라라

#메모이제이션 추가
# 뒤에서 부터 생각. 초기값을 무조건 첫 칸으로 주면 마지막을 꼭 밟아야 한다는 조건 충족.
m=int(input())
lst=[] 
for _ in range(m):
  lst.append(int(input()))

lst.reverse()

memo={}

def stairs(lst,cur, n, cont):
  #cur: 현재 위치  n: 계단 총 갯수
  #cont: 연속으로 몇번 올랐는지. 1이면 무조건 다다음꺼 밟아야함.

  next, n_next = 0,0

  #마지막 계단
  if cur>=n-1:
    return 0

  #마지막 전계단
  if cur == n-2 and cont < 1:
    return lst[cur+1]
  elif cur == n-2 and cont == 1:
    return 0

  #Memoization. 중복계산 방지
  if (cur, cont) in memo:
    return memo[(cur, cont)]

  #이미 연속 2개이면 무조건 다다음꺼 밟기
  if cont==1:
    n_next=lst[cur+2]+stairs(lst,cur+2,n ,0)  #다다음꺼 밟았으니 연속 0으로 초기화
    return n_next
 
  #연속이 <1인 경우 다음꺼/다다음꺼 모두 가능
  next=lst[cur+1]+stairs(lst,cur+1,n,cont+1) #연속변수+1
  n_next=lst[cur+2]+stairs(lst,cur+2,n ,0)  #연속 0으로 초기화

  res=max(next,n_next)
  memo[(cur, cont)]=res

  return res

print(stairs(lst,0,m,0)+lst[0]) #마지막계단(reverse했으니 index는 0) 무조건 밟음

1. #마지막 전 계단#에서 조건을 elif로 써주지 않고 else: return 0 으로 써주는 바람에 자꾸 0이 나왔다.

else로 써주면 아무 계단 아무 cont에서나 다 0이 된다..

 

2. 초기값을 첫 값으로 설정해주더라도 뒤에서 +=가 아니라 =로 값을 재정의해버리기 때문에 초기값이 의미가 없다.

그래서 마지막 결과값에 그냥 더해주었다.

 예상했지만 메모리와 시간은 동일. 그렇지만 뒤에서부터 접근한다는 생각이 흥미로웠다!