[Silver II] 원숭이 매달기 - 2716 (Java)

 

문제 요약

깊은 아마존 정글에 거대한 나무들에서 갈색 원숭이들이 매우 좋아하는 무화과가 열리고, 이 나무에는 향나무노린재들이 서식하고 있다.

나무 꼭대기에 도달하기 위해서 원숭이들은 매우 조심스럽게 나무에 올라가는 길을 찾아야 한다. 거대한 나무는 부서지기 쉬운 덩굴들이 있는데 이 덩굴들은 시소의 원리와 비슷하다. 덩굴의 무게가 불균형하면 그 덩굴은 끊어지며 그 원숭이들은 땅으로 떨어져 버린다. 원숭이들은 서로 협력하여 덩굴의 균형을 유지한다면 그들은 모두 무화과가 열리고 향나무노린재들이 서식하는 나무 꼭대기에 도달할 수 있다는 것을 발견했다.

덩굴은 두개의 덩굴로 나눠질 수 있는데 덩굴이 끊어지지 않기 위해서는 나눠진 두 덩굴은 같은 수의 원숭이들이 매달려 있어야 한다. 덩굴의 나눠지는 지점을 "[]"로 정의 내리면 덩굴의 구조를 꺾쇠괄호로 표시할 수 있다. 또한 덩굴의 깊이는 25를 넘지 않는다.

원숭이들은 덩굴의 균형을 유지하면서 나무꼭대기에 도달할 수 있는 최소 원숭이 수를 알고 싶다. 나무 꼭대기에 도달하기 위해서 최소 한 마리 원숭이가 필요하다.

---

문제 분석

어떤 노드로부터 맨 위까지 갈림길이 최대 N개 존재한다면, 원숭이는 2^N의 배수 마리가 필요하다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < T; i++) {
            System.out.println(calculateMonkeys(br.readLine()));
        }
    }

    private static int calculateMonkeys(String input) {
        int depth = 0;
        int maxDepth = 0;

        for (char c : input.toCharArray()) {
            if (c == '[') {
                depth++;
            } else {
                depth--;
            }
            maxDepth = Math.max(maxDepth, depth);  // 최대 깊이를 추적
        }

        return (int) Math.pow(2, maxDepth);  // 원숭이의 수 = 2^최대깊이
    }
}

package Week22;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_2716 {

    public static void main(String[] args) throws IOException {
        // 입력을 읽기 위한 BufferedReader 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 테스트 케이스의 수를 읽음
        int T = Integer.parseInt(br.readLine());

        // 각 테스트 케이스를 처리
        for(int i = 0; i < T; i++){
            // 각 테스트 케이스마다 calculateMonkeys 함수의 결과를 출력
            System.out.println(calculateMonkeys(br.readLine()));
        }
    }

    private static int calculateMonkeys(String input) {
        // 원숭이의 총 수 초기화 (기본 케이스)
        int totalMonkeys = 1;

        // 나무의 현재 깊이를 추적하기 위한 변수
        int currentDepth = 0;

        // 각 깊이에서의 새로운 가지(따라서 원숭이)의 수를 저장하기 위한 배열
        int[] monkeysIncrementByDepth = new int[150];

        // 입력이 비어 있다면 원숭이는 한 마리만 있음 (기본 케이스)
        if(input.isEmpty()){
            return totalMonkeys;
        }

        // 입력 문자열의 각 문자를 처리
        for(char c : input.toCharArray()){
            if(c == '['){
                // 새로운 가지 발견, 즉 새로운 원숭이, 현재 깊이의 카운터 증가
                monkeysIncrementByDepth[currentDepth++]++;
            } else {
                // 현재 가지의 끝, 깊이 감소
                currentDepth--;
            }
        }

        // 각 깊이에서의 증가량을 기반으로 원숭이의 총 수를 계산
        for(int i = 0; i < monkeysIncrementByDepth.length; i++){
            if(monkeysIncrementByDepth[i] == 0){
                break;  // 더 깊은 깊이에서 원숭이가 더 이상 없음
            }
            totalMonkeys *= 2;  // 각 새로운 가지에 대해 원숭이 수를 두 배로 함
        }
        return totalMonkeys;  // 계산된 원숭이의 총 수를 반환
    }
}

---

참고

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kks227&logNo=220444375611 

[2716번] 원숭이 매달기