본문 바로가기
Computer Science/Baekjoon

[Baekjoon] 2579번 계단 오르기 S3

seungjoonH 2025. 1. 23. 18:41

2579번 - 계단 오르기

1. 문제

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

2579-1

<그림 1>

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

2579-2

<그림 2>

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

첫째 줄에 $N (1 ≤ N ≤ 1,000,000,000)$ 이 주어진다.

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

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

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

  • Input

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

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

  • Output

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

2. 사용 알고리즘

  1. BFS (너비 우선 탐색)
  2. DP (동적 계획법)

3. 풀이

해당 문제는 너비 우선 탐색 (이하 BFS) 이나 동적 계획법 (이하 DP) 알고리즘을 사용하여 해결할 수 있다.


BFS 으로 구현할 때 시간 초과, 메모리 초과 등 여러 문제가 발생하였고 이를 해결해 나가는 과정이 의미있었다. 더불어 해당 문제를 DP 으로 해결하는 방법도 뒤늦게 알게되어 해당 구현 전개과정도 함께 기록하고자 한다.

3.1. 너비 우선 탐색 풀이

먼저 다음을 정의한다.

  • $m$: 최대 점수 (구해야 할 값)
  • $i$: 계단의 색인
  • $p_i$: $i$ 번째 계단에 할당된 점수
  • $q$: 현재까지 연속된 계단의 수

3.1.1. 과정

너비 우선 탐색 해결법은 다음의 단계를 따른다.

  1. $m = 0$ 으로 초기화 한다.
  2. $(0, \ 0, \ p_0)$ 를 Queue 에 enqueue 한다.
  3. $n > 1$ 일 경우, $(1, \ 0, \ p_1)$ 를 Queue 에 enqueue 한다.
  4. Queue 를 dequeue 한 값을 $(i, \ q, \ p_i)$ 라고 한다.
  5. $i = n - 1$ 일 경우,
    (마지막 계단임)
    $m$ 을 $m$, $p_i$ 값 중 더 큰 값으로 최신화 한다.
  6. $i + 1 \lt n$ 이면서 $q < 1$ 일 경우,
    (바로 다음 계단이 총 계단 범위 내에 있고, 현재까지 계단 선택이 연속되지 않음)
    $(i + 1, \ q + 1, \ p_i + p_{i + 1})$ 를 Queue 에 enqueue 한다.
  7. $i + 2 \lt n$ 일 경우,
    (한 칸 건너 계단이 총 계단 범위 내에 있음)
    $(i + 2, \ 0, \ p_i + p_{i + 2})$ 를 Queue 에 enqueue 한다.
  8. Queue 내에 값이 존재하면 3. 으로 이동한다.

3.1.2. 제출 시 유의사항

  • 시간 초과

    • Queue 내부 원소 간 중복문제를 해결하지 않으면 시간 초과 문제에 직면할 수 있다.


    element 가 Queue 내에 존재하는지 여부를 판단한 후, 없을 경우에 enqueue 한다면 중복 원소를 제거하여 처리 시간을 줄일 수 있다.

    if element not in queue: queue.append(element)

    하지만 여전히 시간 초과 가 발생하였고, 이는 in 예약어가 배열 을 대상으로 사용될 때의 시간복잡도가 $O(n)$ 인 것이 원인이었다.

    element not in queue

    이에 따라 in 예약어의 배열에 대한 사용을 지양하고, 중복 제거 시 일반적으로 사용되며 존재 여부 판단 시간복잡도가 $O(1)$ 인 set 을 대상으로 사용하였다.

    연산 in list() in set()
    시간복잡도 $O(n)$ $O(1)$ 
    def append(element):
  if element in seen: return # O(1)
  queue.append(element)
  seen.add(element)
  • 메모리 초과

    • 하지만 Python 의 set 자료형이 가진 다음의 특성에 따라 메모리 초과 가 발생하였다.

    Python set 의 특성

    • 해시 기반 자료구조
      • 데이터 저장 시 해시 테이블을 사용한다.
    • 동적 크기 조정
      • 해시 테이블의 충돌을 최소화하기 위해 버킷 배열의 크기를 적절히 유지한다.
      • 요소 추가 시 배열 크기를 동적으로 조절한다.
    • 메모리 오버헤드
      • 각 데이터 값과 더불어 해시 값을 저장하는데 추가 공간을 사용한다.
      • 데이터의 중복을 방지하기 위한 계산 과정에도 추가적인 메모리를 사용한다.

    이와 같이 set 에 3개의 원소로 이루어진 tuple 데이터를 저장했기 때문에, 메모리 사용량이 크게 증가하게 되었던 것이다.


    따라서 중복 제거는 Python의 dict 자료형을 사용하여 해결하였다. dict 는 set 과 마찬가지로 해시 테이블을 사용하여 데이터를 저장하지만, 이 코드에서는 중복 제거 시 저장하는 상태를 기존의 3개 원소로 구성된 tuple 에서 2개의 원소로 줄여 메모리 사용량을 감소시켰다. 또한, 기존 방식처럼 반복문 내에서 Queue 에 데이터 존재 여부를 실시간으로 판단하여 데이터를 계속 추가하는 방식이 아니라, 반복문 내부에서 새로운 메모리를 생성하고, 상태를 갱신하는 방식을 도입하였다.

    제출 코드 #6, 제출 코드 #7, 제출 코드 #8


    이 방식에서는 next_memory 가 일종의 Sub Queue 역할을 하며, 현재 단계에서 발생할 수 있는 새로운 상태들을 저장하고 관리한다. 이렇게 하면 불필요하게 Queue의 크기가 계속 증가하지 않으며, 중복 상태를 효율적으로 처리할 수 있다. 반복이 끝날 때마다 memory 를 next_memory 로 교체하여 이전 단계의 데이터를 모두 제거하므로, 메모리 사용량을 효과적으로 제한할 수 있다.


  • 런타임 에러 (IndexError)

    • 계단이 단 1개만 존재할 수 있다는 점을 간과해서는 안 된다. 한 계단 전과 두 계단 전을 비교하는 연산에서, 배열의 크기를 초과하여 접근하려고 시도하면 IndexError 가 발생할 수 있다.

3.2. 동적 계획법 풀이

위 문제를 BFS 으로 해결하였지만, 사실 이 문제의 출제 의도는 DP 로 해결하는 것이었다.

3.2.1. 정의

먼저 다음을 정의한다.

  • $p_i$: $i$ 번째 계단의 점수

3.2.2. 동적 계획 배열(수열)

  • $a_i$: 계단 오르기 게임을 통해 $i$ 번째 계단까지 오를 때 얻을 수 있는 최대 점수

3.2.3. $a_0$

동적 계획 배열의 $0$ 번 원소는 $0$ 으로 초기화한다. 이후 점화식을 통해 이전 원소가 참조될 때 IndexError 가 발생하지 않도록 하는 조치이다.

3.2.4. $a_1$

$1$ 번 원소는 $1$ 번째 계단까지 오를 때 얻을 수 있는 최대 점수로 $p_1$ 이다.

3.3.5. $a_2$

$2$ 번째 계단까지 오를 때 점수를 최대로 만들기 위해서는 반드시 $1$ 번째 계단도 밟아야한다. 따라서 얻을 수 있는 최대 점수는 $p_1 + p_2$ 이다.

3.3.6. $a_n(n \gt 2)$

$n$ 번째 계단에 도달하는 단계 바로 이전 단계는 다음의 경우가 존재한다.

  1. $n - 2$ 번째 계단에서 두 계단을 오른 경우
  2. $n - 3$ 번째 계단에서 두 계단을 오르고, $n - 1$ 번째 계단에서 한 계단을 오른 경우

3.3.7. 점화식

따라서 다음의 점화식을 가진다.

$$ a_n = \begin{cases} 0 & n = 0 \\ p_1 & n = 1 \\ p_1 + p_2 & n = 2 \\ \text{max}( a_{n - 2}, a_{n - 3} + p_{n - 1} ) + p_n & n \gt 2 \\ \end{cases} $$

위 식을 참고하여 DP 를 설계하면 된다.

4. 제출 코드

1차

시간 초과

from collections import deque

n = int(input())
points = [int(input()) for _ in range(n)]
queue = deque([(0, 0, 0, points[0]), (1, 0, 0, points[1])])
max_point = 0

while queue:
  index, sequence, count, point = queue.popleft()
  max_point = max(point, max_point)
  a, b = index + 1, index + 2

  if a < n and sequence < 1:
    next_element = (a, sequence + 1, count + 1, point + points[a])
    if next_element not in queue: queue.append(next_element)

  if b < n:
    next_element = (b, 0, count + 1, point + points[b])
    if next_element not in queue: queue.append(next_element)

print(max_point)

문제점

  • sys.stdin.readline() 함수 미사용
  • 실제 사용되지 않는 count 정보 사용
  • 계단이 1개인 경우 미고려
  • 매번 Queue 에 원소 중복 여부 탐색 (in)
  • 최댓값 최신화 조건 설정 오류

2차

시간 초과

from sys import stdin
from collections import deque

input = stdin.readline

n = int(input())
points = [int(input()) for _ in range(n)]
queue = deque([(0, 0, 0, points[0]), (1, 0, 0, points[1])])
max_point = 0

while queue:
  index, sequence, count, point = queue.popleft()
  max_point = max(point, max_point)
  a, b = index + 1, index + 2

  if a < n and sequence < 1:
    next_element = (a, sequence + 1, count + 1, point + points[a])
    if next_element not in queue: queue.append(next_element)

  if b < n:
    next_element = (b, 0, count + 1, point + points[b])
    if next_element not in queue: queue.append(next_element)

print(max_point)

문제점

  • 실제 사용되지 않는 count 정보 사용
  • 계단이 1개인 경우 미고려
  • 매번 Queue 에 원소 중복 여부 탐색 (in)
  • 최댓값 최신화 조건 설정 오류

3차

메모리 초과

from sys import stdin
from collections import deque

input = stdin.readline

n = int(input())
points = [int(input()) for _ in range(n)]
queue = deque([(0, 0, 0, points[0]), (1, 0, 0, points[1])])
seen = set()
max_point = 0

def append(element):
  if element in seen: return
  queue.append(element)
  seen.add(element)

while queue:
  index, sequence, count, point = queue.popleft()
  max_point = max(point, max_point)
  a, b = index + 1, index + 2

  if a < n and sequence < 1:
    append((a, sequence + 1, count + 1, point + points[a]))

  if b < n:
    append((b, 0, count + 1, point + points[b]))

print(max_point)

문제점

  • 실제 사용되지 않는 count 정보 사용
  • 계단이 1개인 경우 미고려
  • set 자료형에 많은 데이터 할당
  • 최댓값 최신화 조건 설정 오류

4차

메모리 초과

from sys import stdin
input = stdin.readline

n = int(input())
points = [int(input()) for _ in range(n)]
memory = set([(0, 0, 0, points[0]), (1, 0, 0, points[1])])
max_point = 0

def append(element):
  if element in memory: return
  memory.add(element)

while memory:
  index, sequence, count, point = memory.pop()
  max_point = max(point, max_point)
  a, b = index + 1, index + 2

  if a < n and sequence < 1:
    append((a, sequence + 1, count + 1, point + points[a]))

  if b < n:
    append((b, 0, count + 1, point + points[b]))

print(max_point)

문제점

  • 실제 사용되지 않는 count 정보 사용
  • 계단이 1개인 경우 미고려
  • set 자료형에 많은 데이터 할당
  • 최댓값 최신화 조건 설정 오류

5차

메모리 초과

from sys import stdin
from collections import deque

input = stdin.readline

n = int(input())
points = [int(input()) for _ in range(n)]
queue = deque([(0, 0, points[0]), (1, 0, points[1])])
seen = set()
max_point = 0

def append(element):
  if element in seen: return
  queue.append(element)
  seen.add(element)

while queue:
  index, sequence, point = queue.popleft()
  max_point = max(point, max_point)
  a, b = index + 1, index + 2

  if a < n and sequence < 1:
    append((a, sequence + 1, point + points[a]))

  if b < n:
    append((b, 0, point + points[b]))

print(max_point)

문제점

  • 계단이 1개인 경우 미고려
  • set 자료형에 많은 데이터 할당
  • 최댓값 최신화 조건 설정 오류

6차

틀렸습니다

from sys import stdin
input = stdin.readline

n = int(input())
points = [int(input()) for _ in range(n)]
memory = {(0, 0): points[0], (1, 0): points[1]}
max_point = 0

while memory:
  next_memory = dict()

  for (index, sequence), point in memory.items():
    max_point = max(point, max_point)
    a, b = index + 1, index + 2

    if a < n and sequence < 1:
      e = (a, sequence + 1)
      p = next_memory[e] if e in next_memory else 0
      next_memory[e] = max(p, point + points[a])

    if b < n:
      e = (b, 0)
      p = next_memory[e] if e in next_memory else 0
      next_memory[e] = max(p, point + points[b])

  memory = next_memory

print(max_point)

문제점

  • 계단이 1개인 경우 미고려
  • 최댓값 최신화 조건 설정 오류

7차

런타임 에러 (IndexError)

from sys import stdin
input = stdin.readline

n = int(input())
points = [int(input()) for _ in range(n)]
memory = {(0, 0): points[0], (1, 0): points[1]}
max_point = 0

while memory:
  next_memory = dict()

  for (index, sequence), point in memory.items():

    if index == n - 1: max_point = max(point, max_point)
    a, b = index + 1, index + 2

    if a < n and sequence < 1:
      e = (a, sequence + 1)
      p = next_memory[e] if e in next_memory else 0
      next_memory[e] = max(p, point + points[a])

    if b < n:
      e = (b, 0)
      p = next_memory[e] if e in next_memory else 0
      next_memory[e] = max(p, point + points[b])

  memory = next_memory

print(max_point)

문제점

  • 계단이 1개인 경우 미고려

8차

맞았습니다!!

from sys import stdin
input = stdin.readline

n = int(input())
points = [int(input()) for _ in range(n)]

memory = {(0, 0): points[0]}
if n > 1: memory[(1, 0)] = points[1]
max_point = 0

while memory:
  next_memory = dict()

  for (index, sequence), point in memory.items():

    if index == n - 1: max_point = max(point, max_point)
    a, b = index + 1, index + 2

    if a < n and sequence < 1:
      e = (a, sequence + 1)
      p = next_memory[e] if e in next_memory else 0
      next_memory[e] = max(p, point + points[a])

    if b < n:
      e = (b, 0)
      p = next_memory[e] if e in next_memory else 0
      next_memory[e] = max(p, point + points[b])

  memory = next_memory

print(max_point)

9차

맞았습니다!!

from sys import stdin
input = stdin.readline

n = int(input())
points = [int(input()) for _ in range(n)]
dp = [0] * n

dp[0] = points[0]
if n > 2: dp[1] = points[0] + points[1]

for i in range(2, n):
  dp[i] = max(dp[i - 2], dp[i - 3] + points[i - 1]) + points[i]

print(dp)

5. 반례모음

다음으로 풀이에 도움이 될만한 반례를 기술한다.

반례1

배열 범위 초과: 런타임 에러 (IndexError)

  • 입력
1
100
  • 정답
100

반례2

시간 초과

  • 입력
300
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
  • 정답
30200

관련 포스팅

728x90
저작자표시

'Computer Science > Baekjoon' 카테고리의 다른 글

[Baekjoon] 풀이 및 포스팅 목록  (0) 2024.10.14
[Baekjoon] 1262번 알파벳 다이아몬드 S1 <Short>  (0) 2024.09.22
[Baekjoon] 15723번 n단 논법 S1  (0) 2024.08.23
[Baekjoon] 1022번 소용돌이 예쁘게 출력하기 G3 <Short>  (0) 2024.08.19
[Baekjoon] 10101번 삼각형 외우기 B4 <Short>  (1) 2024.01.20

'Computer Science/Baekjoon' Related Articles

티스토리툴바