문제 3004
세그 어쩌고 나무
문제 설명과 제한, 예시, 제출 가이드를 확인하고 바로 제출할 수 있습니다.
문제 설명
RTX 2147483647.jpg
“세그 어쩌고 나무” 라는 자료구조에서, 크기 N인 “세그 어쩌고 나무”를 만들기 위해서는
(N 이상의 가장 작은 2의 거듭제곱) × 2 개의 메모리가 필요하다.
평소 이를 계산하기 귀찮아 걍 4배로 설정해놓던 jbs33_PJW는,
자신의 컴퓨터 메모리가 0.008TB밖에 되지 않는다는 사실을 알고 메모리를 절약하려 한다.
크기 N의 “세그 어쩌고 나무”를 만들기 위해 필요한 메모리의 개수를 구하시오.
입력 설명
첫째 줄에 크기 N이 주어진다. (2 ≤ N ≤ 108)
출력 설명
첫 번째 줄에 필요한 메모리의 개수를 출력한다.
입력 예시
31
출력 예시
64
힌트
예시 입력에서 31 이상의 가장 작은 2의 거듭제곱은 32이다.
따라서 32 * 2 = 64가 답이 된다.
N 이상이므로 N이 2의 거듭제곱이라면, 2N이 출력되어야 함에 유의하라.
예를 들어 입력으로 8이 주어졌다면 32가 아닌 16이 출력되어야 한다.
(여담으로, “세그 어쩌고 나무” 의 정식 명칭은 “세그먼트 트리” 이다.)
따라서 32 * 2 = 64가 답이 된다.
N 이상이므로 N이 2의 거듭제곱이라면, 2N이 출력되어야 함에 유의하라.
예를 들어 입력으로 8이 주어졌다면 32가 아닌 16이 출력되어야 한다.
(여담으로, “세그 어쩌고 나무” 의 정식 명칭은 “세그먼트 트리” 이다.)
출처
프로그래밍챌린지 AND2024