문제
포화 이진 트리 형태의 알파벳 트리 장난감이 있다. 이 장난감의 각 노드에는 알파벳이 쓰여있고, 루트 노드의 윗부분에는 구멍이 나 있다. 이 구멍을 통해 공을 넣으면 50%의 확률로 왼쪽 또는 오른쪽 자식 노드로 공이 굴러간다. 그렇게 공은 리프 노드에 도달할 때까지 계속 굴러간다. 여기서 전체 장난감의 높이가 N일 때, 루트 노드의 높이는 1, 리프 노드의 높이는 N에 해당한다.
공이 한 번 들어간 노드는 불이 켜지기 때문에, 공이 어떤 경로를 통해 굴러내려 왔는지 알 수 있다. 공을 한 번 굴리면 점수를 얻을 수 있는데, 각 알파벳의 점수를 A가 1점, B가 2점, ..., Z가 26점 이라고 할 때 경로에 포함된 알파벳들의 점수 합이 곧 경로의 점수가 된다. 장난감에 공을 굴렸을 때 얻을 수 있는 점수의 최솟값과 최댓값을 각각 구해보자.
입력
첫째 줄에 알파벳 트리 장난감의 높이 N이 주어진다.
다음 N개의 줄에는 알파벳 트리 장난감의 노드에 적힌 문자가 주어진다.
i(1 ≤ i ≤ N) 번째 줄에는 2^(i-1) 개의 문자가 주어지고, 해당 높이의 가장 왼쪽에 위치한 노드에 적힌 문자부터 순서대로 주어진다.
- 3 ≤ N ≤ 20
- 주어지는 문자는 모두 알파벳 대문자이다.
import sys
input = sys.stdin.readline
n = int(input())
s = [[]]
min_result, max_result = 9**9, 0
for i in range(1, n+1):
s.append(input().rstrip())
def dfs(hight, cur_node, score):
score += ord(s[hight][cur_node]) - ord('A') + 1
if hight < n:
dfs(hight+1, cur_node*2, score)
dfs(hight+1, cur_node*2+1, score)
else:
global min_result, max_result
min_result = min(min_result, score)
max_result = max(max_result, score)
dfs(1, 0, 0)
print(min_result)
print(max_result)
바로 DFS 로 풀어야하는 문제라고 생각했다. 재귀함수를 써야한다는 압박에 당황했지만, 포화 이진 트리라는 점이 경우의 수를 단순화 시켜줬다.
※출처
https://multicampus-kdt.goorm.io/lecture/38996/멀티잇-코딩테스트-러닝클래스-python-6월반