연습문제 2-5(4) 포화 이진 트리 노드 개수

문제 설명

포화 이진 트리(Perfect binary tree)란, 리프 노드를 제외한 모든 노드가 2개의 자식 노드를 가지는 트리를 말합니다.

높이가 n인 포화 이진 트리의 전체 노드 수를 구하려고 합니다.

높이 n이 주어질 때, 트리의 모든 노드 개수를 출력하는 프로그램을 구현하세요.

결괏값이 매우 클 수 있으니, 결과를 1,000,000,007로 나눈 나머지 값을 반환해 주세요.

  · 참고 : 포화 이진 트리의 구조(출처 : https://iq.opengenus.org/perfect-binary-tree/) 

 

---

입력 형식

· n : 포화 이진 트리의 높이(정수)

---

출력 형식

· 높이가 n인 포화 이진 트리의 노드의 개수를 정수로 반환

---

제약 사항

· 1 <= n <= 1000000

---

입출력 예시

· 입력

  · n = 5

· 출력 : 31

· 설명 : 높이 1~5까지 각각 노드 개수가 1, 2, 4, 8, 16으로, 이를 모두 더하면 31이 된다.

---

작성 코드

class Solution254 {
    public int solution(int n) {

        int result = 1;

        for (int i = 1; i < n; i++) {
            result = (result * 2 + 1) % 1000000007;
        }
        return result;
    }

    public static void main(String[] args) {
        Solution254 st = new Solution254();
        int n = 5;
        System.out.println(st.solution(n));
    }
}

 

정답 코드

class Solution {
    static int MOD = 1_000_000_007;

    public int solution(int n) {
        int result = 1;
        for (int i = 0; i < n; i++) {
            result *= 2;
            result %= MOD;
        }
        return result - 1;
    }

    public static void main(String[] args) {
        Solution st = new Solution();
        int n = 5;
        System.out.println(st.solution(n));
    }
}