4457번 - 상근이의 자물쇠 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 32 | 14 | 12 | 54.545% |
문제
상근이는 학교 사물함에 매우 비싼 물건을 보관한다. 이렇게 중요한 물건을 학교에 보관하는 이유와 무엇이 그렇게 중요한지는 아직 알려지지 않았다. 하지만, 상근이는 보안을 유지하기 위해서 비밀번호가 9자리인 자물쇠를 이용한다.
이 자물쇠에는 LED 디스플레이가 있다. 상근이가 자물쇠를 만지면 자물쇠는 디스플레이에 숫자 하나를 보여준다. 이 숫자를 N이라고 했을 때, 다음과 같은 조건을 만족하는 트리의 개수의 마지막 9자리를 입력하면 자물쇠는 열린다.
노드가 N개있는 이진 트리가 있다. 이때, 각 노드의 오른쪽 서브트리와 왼쪽 서브트리의 높이의 차이는 1이내이다. 서브트리의 높이란 그 서브트리의 루트와 리프 노드와의 경로의 길이 중에서 가장 긴 값이다. 노드가 하나있는 서브트리의 높이는 0이고, 노드가 없는 서브트리의 높이는 -1이다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 정수 하나 N으로 이루어져 있다. N은 1보다 크거나 같고, 1427보다 작거나 같은 자연수이다.
출력
입력으로 주어진 N에 해당하는 트리의 개수의 마지막 9자리를 출력한다. (0을 출력해서 9자리로 맞춰야 한다)
예제 입력 1
1 3 6 21
예제 출력 1
000000001 000000001 000000004 000036900
출처
ICPC > Regionals > North America > Pacific Northwest Regional > 2011 Pacific Northwest Region Programming Contest K번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호