-
2579. [Python]계단 오르기Python_알고리즘/Silver III 2023. 2. 6. 01:21
1. 문제
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- 규칙 파악
- DP
3. 파이썬 코드
N = int(input()) # 계단의 값 리스트 배열 생성 work_list = [0] # 각 계단의 최대값 저장 배열 생성 max_list = [0]*301 # 계단의 값 추가 for _ in range(N): work_list.append(int(input())) # 계단의 최대 칸 수만큼 반복문 시행 for i in range(1,N+1): # 계단이 1개일 경우 최대값은 그 계단의 값 if i == 1: max_list[i] = work_list[i] # 계단이 2개일 경우 최대값은 그 계단과 직전의 계단을 더한 값 elif i == 2: max_list[i] = max_list[1] + work_list[i] # 계단이 3개 이상일 경우 그 계단에 도달하는 값이 정해져있다. # 1번 : 바로 직전계단을 밟은것이 아닌 처음과 두번째 계단을 밟고 도착하는 방법 # 2번 : 처음 계단을 밟고 두번째를 건너뛰고 직전계단을 밟고 도착하는 방법 else: max_list[i] = max(work_list[i] + max_list[i-3] + work_list[i-1], work_list[i] + max_list[i-2]) print(max_list[N])
4. 문제를 풀고난 후 생각
- 각자 계단에서 나올 수 있는 최대값들을 생각해서 배열을 만들어 집어넣을 생각을 했다.
- 각 계단의 값들이 얼마들어있는지 리스트를 생성하였고, 최대 300칸의 계단이 들어오기 때문에 배열을 0~300 까지 생성하였다.
- 이후 각 계단에서 나올 수 있는 최대값을 계산하는 방법을 생각해본다.
- 방법 1 : 계단에 도착하기 직전 계단을 제외한 두칸 전과 세칸 전의 계단을 밟고 도착한 경우
- 방법 2 : 계단에 도착하기 직전 계단과 세칸전의 계단을 밟은 경우 - 위 두방법이 계단에 도착했을때 값이 나올 수 있는 값들이 된다.
- 방법 1의 경우 내가 도착할 계단에서 두칸전의 계단의 최대값만 가져오면 된다. 그 이유는 이미 그 계단에서 올 수 있는 최대값을 계산해뒀기 때문에 그 값에 도착했을때 계단의 값만 더해주면 되기 때문에 위에서 식을 저렇게 작성하였다.
- 두 방법의 값중 max값이 되는 값을 max_list 에 추가해주면 된다.
5. 문제를 푸는데 도움이 되는 지식
- DP
'Python_알고리즘 > Silver III' 카테고리의 다른 글
1515. [Python]수 이어 쓰기 (0) 2023.04.14 14425. [Python]문자열 집합 (0) 2023.03.01 2108. [Python]통계학 (0) 2023.02.25 1463. [Python]1로 만들기 (0) 2023.02.11 17413. [Python]단어 뒤집기 2 (0) 2023.02.05