SWEA 5178ノードの和
7702 ワード
問題のソースソフトウェアExpert Academy
問題の著作権はSW Expert Academyにあります.
問題の著作権はSW Expert Academyにあります.
質問の概要
5178 노드의합
- 노드갯수 N, 리프노드갯수 M, 출력노드번호 L
- 리프(최하단)노드의 번호와 그 노드의 값이 주어진다.
- 부모노드는 자식노드의 저장된 값의 합이 들어간다.
- 위와 같은 규칙으로 완전이진트리를 만든다고 할 때,
- 지정한 번호의 노드 값을 출력하는 프로그램을 작성
입력:
1
5 3 2 (노드 5개, 리프노드 3개, 출력노드 2)
4 1 (4번 노드 값은 1)
5 2 (5번 노드 값은 2)
3 3 (3번 노드 값은 3)
출력:
#1 3 (2번 노드의 값은 3, 자식노드의 값 1 + 2, 자식노드 = 4번, 5번노드)
プールアクセス
1. 노드의 개수(N)만큼 완전이진트리를 만듦
2. 입력받은 리프노드 값을 트리에 대입
2. 부모노드(i//2)에 자식노드의 값을 더함
コード#コード#
for tc in range(int(input())):
# 노드 N개, 리프노드 M개, 출력노드 L번
N, M, L = map(int, input().split())
tree = [0 for _ in range(N+1)] # 루트노드 번호가 1이니 +1
for _ in range(M): # 리프노드번호와 값 입력받고 트리에 대입
idx, value = map(int, input().split())
tree[idx] = value
for i in range(N, 0, -1):
# 마지막 노드부터 역순으로 부모노드 값 대입
if i // 2 > 0:
tree[i//2] += tree[i]
print(f'#{tc+1} {tree[L]}')
1
5 3 2
4 1
5 2
3 3
#1 3
定義された変数値の決定
tree
[0, 6, 3, 3, 1, 2]
i # i는 N부터 역순으로 1까지
1
Reference
この問題について(SWEA 5178ノードの和), 我々は、より多くの情報をここで見つけました https://velog.io/@wltn39/SWEA-5178-노드의-합テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol