<stdio.han>

백준 1182번: 부분수열의 합[JAVA]

https://www.acmicpc.net/problem/1182

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N, S, result = 0;
    static int[] subsequence;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken()); // 정수의 개수
        S = Integer.parseInt(st.nextToken()); // 타깃 넘버
        subsequence = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            subsequence[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0);


        if (S == 0) { // S가 0일 때 result--
            result--;
        }
        System.out.println(result);


        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int depth, int sum) {
        if (depth == N) { // depth 가 마지막까지 갔을 경우
            if (sum == S) { // 그 중에 sum 이 타깃 넘버일 경우
                result++;
            }
            return;
        }
        dfs(depth + 1, sum + subsequence[depth]); // 원소를 선택했을 경우의 수열의 합
        dfs(depth + 1, sum); // 원소를 선택하지 않았을 경우의 수열의 합
    }
}

[설명]

이 문제는 브루트 포스 알고리즘 그중에 dfs알고리즘을 이용해 풀수있는 문제이다. 문제 설명을 하자면 숫자가 주어지면 그 수를가지고 만들 수 있는 모든 부분수열을들중 부분수열들의 합이 S 인 경우의 수를 출력하는 문제이다.

예를 들면 숫자가 1, 2, 3 이 주어졌다면 가능한 부분수열은 {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, {3} 이다. 수열들의 모습을 보면 브루트포스 알고리즘을 활용했을때의 결과 같이 생겼다.

코드로 구현했을 경우 한 가지 문제가 있다. S가 0일경우이다.  dfs 로직을 실행할 때 부분수열들의 합이 담기는 변수 sum 이 처음에 0을 초기화가 되어있기 때문에 원소를 아무것도 선택하지 않는다면 부분수열의 합이 0이라고 계산되기 때문이다. 그렇기 때문에 S가 0일경우 마지막에 결과값에 1을 빼주어야한다.

백준 1759번: 암호 만들기[JAVA]

https://www.acmicpc.net/problem/1759

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    static int L, C;
    static char[] code;
    static char[] arr;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        L = Integer.parseInt(st.nextToken()); // 암호의 길이
        C = Integer.parseInt(st.nextToken()); // C개의 소문자

        code = new char[L]; // 암호를 저장할 배열
        arr = new char[C]; // 알파벳 입력받을 배열

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < C; i++) {
            arr[i] = st.nextToken().charAt(0); // 초기화
        }
        Arrays.sort(arr); // 사전순으로 정렬

        dfs(0, 0); //로직 실행
    }

    public static void dfs(int depth, int start) {
        // depth 가 L일 경우 종료
        if (depth == L) {
            if (isValid(code)) { // 자음,모음 체크하는 로직 실행 후 true 일 경우에만 출력
                for (char c : code) {
                    System.out.print(c);
                }
                System.out.println();
            }
            return;
        }
        for (int i = start; i < C; i++) {
            code[depth] = arr[i]; // 코드배열 입력
            dfs(depth+1, i+1); // depth 한칸 깊이, start 위치 한칸 이동
        }
    }

    // 자음이 2개이상 모음이 1개 이상인지 판별하는 로직
    public static boolean isValid(char[] code) {
        int c = 0; // 자음의 수
        int v = 0; // 모음의 수
        for (int i = 0; i < code.length; i++) {
            if (code[i] == 'a' || code[i] == 'e' || code[i] == 'i' || code[i] == 'o' || code[i] == 'u') {
                v++; // 모음일 경우 v++
            } else {
                c++; // 자음일 경우 c++
            }
        }
        if (c >= 2 && v >= 1) {
            return true; // 자음 2개 이상, 모음 1개이상 일 경우 true 반환
        } else {
            return  false; // 아닐경우 false 반환
        }
    }
}

[설명]

완전탐색(브루트 포스) 알고리즘을 이용해 문제를 풀었다. 그 이유는 '해' 가 가능한 모든 경우의 수를 탐색한 후, 조건에 해당하는 해를 '모두' 출력해야하는 문제이기 때문이다. 완전탐색 알고리즘 중의 하나인 DFS 알고리즘을 이용해 문제를 풀었다.

문제의 해결방법의 순서를 대략적으로 설명하자면

1. 문자열을 입력받는다.

2. 입력받은 문자열을 이용해 depth 가 L이 될때 까지 dfs 를 한다.

3. 결과값이 조건을 통과할 경우 출력한다.