728x90

 

[16198] 에너지 모으기 성공

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초 512 MB 6597 4967 4024 76.270%

문제

N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.

i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

  1. 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
  2. x번째 에너지 구슬을 제거한다.
  3. W × W의 에너지를 모을 수 있다.x+1
  4. x-1
  5. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.

N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.

둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

출력

첫째 줄에 모을 수 있는 에너지의 최댓값을 출력한다.

문제풀이

이 문제는 DFS + 백트래킹을 활용하여 가능한 모든 구슬 제거 순서를 탐색하고, 최대 에너지 값을 찾는 문제이다.

핵심은 각 단계에서 유효한 구슬을 제거하면서 에너지 누적 합을 계산하는 것

알고리즘 선택 이유

  1. 작은 입력 크기: N ≤ 10 → 완전 탐색 가능
  2. 순열 생성 필요: 구슬 제거 순서에 따라 결과가 달라짐
  3. 최적 부분 구조: 각 단계의 선택이 최종 결과에 영향을 미침

핵심 변수 설명

변수명 역할

maxEnergy 최대 에너지 값 저장
current 현재 남은 구슬 리스트
total 현재까지 누적된 에너지

BaseCase

if(current.size() == 2) {
    maxEnergy = Math.max(maxEnergy, total);
    return;
}
  • 목적: 구슬이 2개만 남았을 때 최종 에너지 계산
  • 동작 메커니즘:
    • current.size() == 2: 첫 번째와 마지막 구슬만 남은 상태 (문제 규칙상 더 이상 제거 불가)
    • total: 현재까지 누적된 에너지 합
    • maxEnergy: 모든 경로 중 최대값 갱신

Recursive Case (탐색 로직)

for(int i=1; i<current.size()-1; i++) {
    int energy = current.get(i-1) * current.get(i+1);
    List<Integer> next = new ArrayList<>(current);
    next.remove(i);
    dfs(next, total + energy);
}
  • 범위 제한: **i=1**부터 **size()-2**까지 → 첫/끝 구슬 제외
  • 에너지 계산:
  • → current.get(i-1) * current.get(i+1) (제거할 구슬의 양쪽 값 곱)
  • 상태 복제:→ 원본 리스트 훼손 방지
  • → **new ArrayList<>(current)**로 독립적인 리스트 생성
  • 재귀 호출:
  • → 제거된 리스트(next)와 누적 에너지(total + energy) 전달
  • 예시 과정
    • current: [1, 2, 3, 4] ****

전체코드

import java.util.*;

class Main {
    static int maxEnergy = Integer.MIN_VALUE;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> current = new ArrayList<>();
        for(int i=0; i<n; i++) current.add(sc.nextInt());
        
        dfs(current, 0);
        System.out.println(maxEnergy);
    }
    
    static void dfs(List<Integer> current, int total) {
        if(current.size() == 2) {
            maxEnergy = Math.max(maxEnergy, total);
            return;
        }
        
        for(int i=1; i<current.size()-1; i++) {
            int energy = current.get(i-1) * current.get(i+1);
            List<Integer> next = new ArrayList<>(current);
            next.remove(i); // i번째 구슬 제거
            dfs(next, total + energy); // 새로운 리스트 전달
        }
    }
}

[2800] 괄호 제거

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초 128 MB 8571 3386 2477 37.627%

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(22)+2)에서 괄호를 제거하면, (2+22+2), 2+(22)+2, 2+22+2를 만들 수 있다. 하지만, (2+22)+2와 2+(22+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다.

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

문제 풀이

이 문제는 주어진 수식에서 괄호 쌍을 선택적으로 제거하여 만들 수 있는 모든 수식을 사전순으로 중복되지 않게 정렬하는 문제이다.

핵심 변수

변수명 역할

input 원본 수식 문자열
pairs 괄호 쌍의 시작/종료 인덱스를 저장하는 리스트 ([[start1, end1], [start2, end2], ...])
results 생성된 수식 저장 (중복 제거 및 정렬을 위해 TreeSet 사용)
selected[] DFS 탐색 시 각 괄호 쌍의 선택 여부 저장

Base Case (종료 조건)

if (depth == pairs.size()) {
    *// ... 문자열 생성 로직 ...*
    if (!sb.toString().equals(input)) {
        results.add(sb.toString());
    }
    return;
}
  • 동작 조건: 모든 괄호 쌍에 대한 선택/제거 결정 완료 (depth == pairs.size())
  • 핵심 로직:
    1. remove[] 배열을 통해 제거할 괄호 위치 마킹
    2. 마킹된 괄호를 제외한 문자열 생성
    3. 원본 수식과 다르면 결과 저장 (**TreeSet**이 자동 정렬 및 중복 제거)

Recursive Case (탐색 로직)

*// 현재 괄호 쌍 유지*
selected[depth] = true;
dfs(depth + 1, selected);

*// 현재 괄호 쌍 제거*
selected[depth] = false;
dfs(depth + 1, selected);
  • 분기 전략:
    • 선택 유지: selected[depth] = true → 해당 괄호 쌍 보존
    • 선택 제거: selected[depth] = false → 해당 괄호 쌍 제거
  • 재귀 구조: 각 괄호 쌍에 대해 2가지 선택지 탐색 → O(2^N) 복잡도 (N=괄호 쌍 수)

동작 예시

입력: (1+(2+3))

괄호 쌍: (인덱스 0-5), (인덱스 3-5)

가능한 결과:

1+(2+3)
(1+2+3)
1+2+3

주요 로직 상세

  1. 괄호 쌍 탐색:
    • 스택을 이용해 중첩 괄호의 짝 정확히 매칭
  2. Stack<Integer> stack = new Stack<>(); for (int i = 0; i < input.length(); i++) { if (input.charAt(i) == '(') stack.push(i); else if (expression.charAt(i) == ')') pairs.add(new int[]{stack.pop(), i}); }
  3. 결과 문자열 생성:
    • 선택되지 않은 괄호 쌍의 시작/종료 인덱스를 **remove[]**에 표시
  4. for (int i = 0; i < pairs.size(); i++) { if (!selected[i]) { *// 제거 대상 괄호* remove[pairs.get(i)[0]] = true; remove[pairs.get(i)[1]] = true; } } for (int i = 0; i < input.length(); i++) { if (!remove[i]) sb.append(input.charAt(i)); }

전체 코드

import java.util.*;

class Main {
    static String input;
    static Set<String> result = new TreeSet<>();
    static List<int[]> pairs = new ArrayList<>();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        input = sc.next();
        
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '(') {
               stack.push(i);
            } else if (input.charAt(i) == ')') {
               pairs.add(new int[]{stack.pop(), i});
            }
        }
                                          
        dfs(0, new boolean[pairs.size()]);
        
        for (String res: result) {
            System.out.println(res);
        }
    }
                                  
    static void dfs(int depth, boolean[] selected) {
        if (depth == pairs.size()) {
           StringBuilder sb = new StringBuilder();
           boolean[] remove = new boolean[input.length()];
            
           for (int i = 0; i < pairs.size(); i++) {
            if (!selected[i]) {
                remove[pairs.get(i)[0]] = true;
                remove[pairs.get(i)[1]] = true;
            }
        }
            
           for (int i = 0; i < input.length(); i++) {
            if (!remove[i]) sb.append(input.charAt(i));
           }
               
           
           if (!sb.toString().equals(input)) {
               result.add(sb.toString());
           }
           return;
        }
        
        selected[depth] = true;
        dfs(depth + 1, selected);
        
        selected[depth] = false;
        dfs(depth + 1, selected);
    }
}

[7490] 0 만들기

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초 128 MB 11777 5912 4418 48.888%

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

문제풀이

이 문제는  1부터 N까지의 숫자를 순서대로 배치하고, 각 숫자 사이에 +, -, 공백( ``)을 삽입하여 수식을 만들 때, 결과가 0이 되는 모든 수식을 찾는 문제이다.

필요 변수

변수명 설명

N 입력으로 주어진 최종 숫자 (예: N=3 → 1, 2, 3 사용)
result 결과가 0이 되는 수식들을 저장하는 리스트 (ArrayList<String>)
op 사용 가능한 연산자 배열 (+, -, 공백)
currentString DFS 탐색 중 현재까지 생성된 수식 문자열

Base Case (종료 조건)

if (depth == N) {
    if (calculate(currentString) == 0) 
        result.add(currentString);
    return;
}
  • 동작 조건: 모든 숫자를 사용했을 때 (depth == N)
  • 로직: 현재 수식을 계산하여 0이면 결과에 추가합니다.

Recursive Case (탐색 로직)

for (int i = 0; i < 3; i++) {
    dfs(depth + 1, currentString + op[i] + (depth + 1));
}
  • 동작: 각 단계에서 +, , 공백을 순차적으로 시도합니다.
  • 예시: 현재 수식이 **"1+2"**일 때, 다음 단계는 "1+2+3", "1+2-3", **"1+23"**입니다.

계산 함수 (calculate)

static int calculate(String str) {
    str = str.replace(" ", ""); *// 공백 제거*
    String[] tokens = str.split("(?=[+-])"); *// 연산자 기준 분할*
    int result = Integer.parseInt(tokens[0]); *// 첫 숫자 초기화*

    for (int i = 1; i < tokens.length; i++) {
        String token = tokens[i];
        int num = Integer.parseInt(token.substring(1)); *// 연산자 뒤 숫자 추출*
        if (token.charAt(0) == '+') {
            result += num;
        } else {
            result -= num;
        }
    }
    return result;
}

1️⃣ split("(?=[+-])") 설명

  • 정규식: **(?=[+-])**는 **전방 탐색(lookahead)**으로, + 또는  바로 앞에서 분할합니다.
  • 예시:"12-34" → ["12", "-34"]
  • "1+2-3" → ["1", "+2", "-3"]

2️⃣ substring(1) 설명

  • 기능: 문자열에서 첫 번째 문자(연산자)를 제외한 나머지 부분을 추출합니다.
  • 예시:"-45".substring(1) → "45"
  • "+123".substring(1) → "123"

전체 코드

import java.util.*;
import static java.util.stream.Collectors.toList;

class Main {
    static int N;
    static List<String> result = new ArrayList<>();
    static String currentString;
    static String[] op = new String[]{"+","-"," "};
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        while (T --> 0) {
            N = sc.nextInt();
        
            dfs(1, "1");
        
            Collections.sort(result);
        
            for (String str : result) {
                System.out.println(str);
            }
            
            System.out.println();
            result.clear();
        }        
    
    }

    static void dfs(int depth, String currentString) {
        if (depth == N) {
            if (calculate(currentString) == 0) 
                result.add(currentString);

            return;
        }

        for (int i = 0; i <3; i++) {
            dfs(depth + 1, currentString + op[i] + (depth + 1));
        }
        
    }
    
    static int calculate(String str) {
        str = str.replace(" ", "");
        String[] tokens = str.split("(?=[+-])");
        int result = Integer.parseInt(tokens[0]);
    
        for(int i = 1; i < tokens.length; i++) {
            String token = tokens[i];
            int num = Integer.parseInt(token.substring(1));
            if (token.charAt(0) == '+') {
                result += num;
            } else {
                result -= num;
            }
        }
        return result;
    }

}
728x90

'알고리즘 > Recursion' 카테고리의 다른 글

[코딩테스트] [2529] 부등호 & [9095] 1,2,3 더하기 & [12101] 1,2,3 더하기 2  (1) 2025.03.25
[코딩테스트] [1759] 암호 만들기 & [10971] 외판원 순회 2 & [14888] 연산자 끼워넣기  (2) 2025.02.19
[코딩테스트] [1182] 부분수열의 합 & [2758] 로또 & [1208] 부분 수열의 합2  (0) 2025.02.12
[코딩테스트] [14267] 회사 문화 1 & [1068] 트리 & [5639] 이진 검색 트리  (0) 2025.02.12
[코딩테스트] [11725] 트리의 부모 찾기 & [1991] 트리 순회 & [15681] 트리와 쿼리  (0) 2025.02.11

티스토리툴바