κ°λ°/π€ μκ³ λ¦¬μ¦
β‘οΈ baekjoon. 14501 ν΄μ¬ [Silver III][python]
ttoance
2023. 6. 28. 11:19
κ΄λ ¨ νμ΄λ₯Ό λ΄€μλ νμλ²μΌλ‘ μ κ·Όν΄μΌ νλ νλ€κ°, μ£Όμ΄μ§ μμ μΌμ΄μ€λ‘ λμ ν μ κ·Όν μκ° μμ΄μ,
dfsλ‘ μ κ·Όν΄μ λͺ¨λ κ²½μ°μ μμ λν΄ κ°μ§κ³ μλ€κ° μ΅λκ°μ 보μ¬μ£Όλ μ κ·Ό λ°©μμ ννλ€.
N = int(input())
results = list()
# history λ³μλ debug μ©λ
def dfs(start, current, history):
if (start >= len(meetingList)):
results.append(current)
return
# μ€λ μ‘νμλ λ―Έν
μ μ§νν κ²½μ°
next = start + meetingList[start][0]
if (next <= len(meetingList)):
dfs(next, current + meetingList[start][1], history + str(start))
# μ€λ μ‘νμλ λ―Έν
μ μ§ννμ§ μμ κ²½μ°
for i in range(start + 1, next):
dfs(i, current, history)
meetingList = list()
for _ in range(N):
meetingList.append(list(map(int, input().split())))
dfs(0, 0, '')
results.sort()
print(results[-1])
+) λ€λ₯Έ νμ΄λ‘λ λμ dpλ‘ μ κ·Όνλ λ°©λ²μ΄ μμ κ² κ°λ€.
https://zu-techlog.tistory.com/42
λ°μν