7354번 - 트리의 순서 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 30 | 25 | 23 | 82.143% |
문제
다음과 과정을 거쳐서 바이너리 트리에 번호를 붙일 수 있다.
- 비어있는 트리의 번호는 0이다.
- 노드가 1개인 트리는 1번이다.
- 노드가 m개인 바이너리 트리의 번호는 m+1개인 트리의 번호보다 작다.
- 노드가 m개이고, 왼쪽과 오른쪽 서브트리가 각각 L과 R인 바이너리 트리의 번호 n은 아래와 같은 두 조건 중 하나라도 만족하는 트리보다 번호가 작다.
- 왼쪽 서브 트리가 L보다 번호가 크다. 또는
- 왼쪽 서브 트리가 L과 같고, 오른쪽 서브트리가 R보다 번호가 크다.
처음 10개 바이너리 트리와 20번째 바이너리 트리를 그림으로 그려보면 아래와 같다.
0 1 2 3 4 5 6 7 8 9 ... 20
X X X X X X X X X X
\ / \ \ / \ / / \ /
X X X X X X X X X X
\ / \ / \ / \
X X X X X X X
\
X
n이 주어졌을 때, n번째 바이너리 트리를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있으며, n이 하나 주어진다. (1 ≤ n ≤ 500,000,000) n=0인 경우에 프로그램을 종료하면 된다.
출력
각각의 n에 대해서, 트리를 아래와 같이 출력한다.
- 자식이 없는 트리는 x로 출력한다.
- 왼쪽, 오른쪽 서브트리가 L과 R이고, 각각을 출력한 결과가 L', R'일 때, (L')x(R')을 출력한다.
- L이 비어잇으면 X(R')을 출력한다.
- R이 비어있으면 (L')x를 출력한다.
예제 입력 1
1 20 31117532 0
예제 출력 1
X ((X)X(X))X (X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)
출처
ICPC > Regionals > North America > East Central North America Regional > 2001 East Central Regional Contest D번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호