문제 링크
문제 요약
주어진 블록체인의 유효성을 검사하고, 유효한 경우 최종 계좌 잔액을 출력하는 문제입니다.
각 블록은 블록 ID, 부모 ID, 거래 금액으로 구성됩니다. 블록체인의 유효성을 판단하는 기준은 다음과 같습니다.
- 제네시스 블록 (첫 번째 블록): 부모 ID가 반드시 0이어야 합니다.
- 체인 연속성: 모든 블록은 자신의 부모 ID가 바로 이전 블록의 블록 ID와 일치해야 합니다. 일치하지 않으면 “INVALID”를 출력합니다.
- 잔액 확인: 어떤 거래가 발생한 후라도 계좌의 잔액이 0보다 작아지면 안 됩니다. 잔액이 음수가 되면 “NO_MONEY”를 출력합니다.
위의 조건 중 하나라도 위반되면 해당하는 메시지를 출력하고 프로그램을 종료합니다. 모든 조건을 통과하면 최종 계좌 잔액을 출력합니다.
풀이
이 문제는 블록체인의 규칙을 순서대로 검사하며 잔액을 추적하는 Simulation 문제입니다.
첫 번째 블록부터 마지막 블록까지 순회하며 각 블록의 유효성을 검사하고, 동시에 현재 잔액을 갱신해야 합니다.
-
제네시스 블록 (첫 번째 블록) 검사:
chain[0]에 해당하는 첫 번째 블록의 부모 ID가 0인지 확인합니다. 만약 0이 아니라면 즉시 “INVALID”를 출력하고 종료합니다.- 첫 번째 블록의 거래 금액(
chain[0][2])으로 현재 잔액을 초기화합니다. - 초기화된 잔액이 0보다 작은지 확인합니다. 만약 그렇다면 “NO_MONEY”를 출력하고 종료합니다.
-
나머지 블록 (두 번째 블록부터) 순차적 검사:
- 두 번째 블록(
chain[1])부터 마지막 블록(chain[N-1])까지 반복문을 돌며 순차적으로 검사합니다. - 각 블록
i에 대해,chain[i]의 부모 ID가chain[i-1](이전 블록)의 블록 ID와 일치하는지 확인합니다. 일치하지 않으면 즉시 “INVALID”를 출력하고 종료합니다. - 현재 블록
i의 거래 금액(chain[i][2])을 현재 잔액에 더합니다. - 잔액을 갱신한 후, 갱신된 잔액이 0보다 작은지 확인합니다. 만약 그렇다면 “NO_MONEY”를 출력하고 종료합니다.
- 두 번째 블록(
-
모든 검사 통과: 위 모든 검사를 통과했다면, 블록체인은 유효하며 최종 잔액을 출력합니다.
정답 코드
def solve():
n = int(input())
chain = [[*map(int, input().split())] for _ in range(n)]
# 제네시스 블록 (첫 번째 블록)의 부모 ID가 0이 아니면 INVALID
if chain[0][1] != 0:
return "INVALID"
current = chain[0][2] # 첫 번째 블록의 거래 금액으로 현재 잔액 초기화
# 초기 잔액이 음수이면 NO_MONEY
if current < 0:
return "NO_MONEY"
# 두 번째 블록부터 마지막 블록까지 순회하며 검사
for i in range(1, n):
parent_id_of_prev_block = chain[i - 1][0] # 이전 블록의 ID
# 현재 블록의 부모 ID가 이전 블록의 ID와 일치하지 않으면 INVALID
if chain[i][1] != parent_id_of_prev_block:
return "INVALID"
current += chain[i][2]
# 거래 후 잔액이 음수이면 NO_MONEY
if current < 0:
return "NO_MONEY"
# 모든 검사를 통과했으면 최종 잔액 반환
return current
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()
print(ret)