## 과제 : 백준 문제 풀이

목표 : 백준 문제를 풀어본다.

- [암호 만들기](https://www.acmicpc.net/problem/1759)
- [N과 M (2)](https://www.acmicpc.net/problem/15650)
- [연산자 끼워넣기](https://www.acmicpc.net/problem/14888)
- [스타트와 링크](https://www.acmicpc.net/problem/14889)

## 과제 : 백준 문제 풀이 모범답안

### 암호 만들기

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int L, C; // L은 암호의 길이, C는 주어진 문자의 개수
    static char[] candidates, password; // 사용 가능한 문자들과 암호를 저장할 배열
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        L = sc.nextInt();
        C = sc.nextInt();
        candidates = new char[C]; // 사용 가능한 문자들을 저장할 배열
        password = new char[L]; // 생성된 암호를 저장할 배열
        
        for (int i = 0; i < C; i++) {
            candidates[i] = sc.next().charAt(0); // 문자를 하나씩 입력받아 배열에 저장
        }
        
        Arrays.sort(candidates); // 사전 순으로 문자를 정렬
        generatePassword(0, 0); // 암호 생성 시작
    }
    
    public static void generatePassword(int start, int depth) {
        if (depth == L) {
            if (isValid(password)) { // 생성된 암호가 조건을 만족하는지 확인
                System.out.println(password); // 조건을 만족하는 암호 출력
            }
            return;
        }
        
        for (int i = start; i < C; i++) {
            password[depth] = candidates[i]; // 현재 위치에 문자를 설정
            generatePassword(i + 1, depth + 1); // 다음 문자를 설정하기 위해 재귀 호출
        }
    }
    
    public static boolean isValid(char[] arr) {
        int vowels = 0; // 모음의 개수
        int consonants = 0; // 자음의 개수
        for (char c : arr) {
            // 모음인지 자음인지 확인하여 각각의 개수를 셈
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                vowels++;
            } else {
                consonants++;
            }
        }
        // 최소 한 개의 모음과 최소 두 개의 자음이 포함되어 있는지 확인
        return vowels >= 1 && consonants >= 2;
    }
}

### N과 M (2)

import java.io.IOException;
import java.util.Scanner;

public class Main {
    static int N, M;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        M = scanner.nextInt();

        arr = new int[M];

        dfs(1, 0);
        System.out.println(sb);
    }

    static void dfs(int start, int depth) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append('\n');
            return;
        }

        for (int i = start; i <= N; i++) {
            arr[depth] = i;
            dfs(i + 1, depth + 1);
        }
    }
}

### 연산자 끼워넣기

import java.util.Scanner;

public class Main {
    static int N;
    static int[] numbers;
    static int[] operators = new int[4]; // +, -, *, /
    static int minValue = Integer.MAX_VALUE;
    static int maxValue = Integer.MIN_VALUE;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = scanner.nextInt();
        }
        for (int i = 0; i < 4; i++) {
            operators[i] = scanner.nextInt();
        }
        scanner.close();

        solve(1, numbers[0]);  // 시작 인덱스와 초기 값
        System.out.println(maxValue);
        System.out.println(minValue);
    }

    public static void solve(int index, int currentResult) {
        if (index == N) {
            minValue = Math.min(minValue, currentResult);
            maxValue = Math.max(maxValue, currentResult);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (operators[i] > 0) {
                operators[i]--;
                switch (i) {
                    case 0:
                        solve(index + 1, currentResult + numbers[index]);
                        break;
                    case 1:
                        solve(index + 1, currentResult - numbers[index]);
                        break;
                    case 2:
                        solve(index + 1, currentResult * numbers[index]);
                        break;
                    case 3:
                        solve(index + 1, currentResult / numbers[index]);
                        break;
                }
                operators[i]++;
            }
        }
    }
}

### 스타트와 링크

import java.util.Scanner;

public class Main {
    static int N;
    static int[][] ability;
    static boolean[] visited;
    static int minDifference = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        ability = new int[N][N];
        visited = new boolean[N];
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ability[i][j] = scanner.nextInt();
            }
        }
        scanner.close();

        divideTeams(0, 0);
        System.out.println(minDifference);
    }

    public static void divideTeams(int index, int count) {
        if (count == N / 2) {
            calculateDifference();
            return;
        }

        for (int i = index; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                divideTeams(i + 1, count + 1);
                visited[i] = false;
            }
        }
    }

    public static void calculateDifference() {
        int teamStart = 0;
        int teamLink = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visited[i] && visited[j]) teamStart += ability[i][j];
                if (!visited[i] && !visited[j]) teamLink += ability[i][j];
            }
        }

        int difference = Math.abs(teamStart - teamLink);
        minDifference = Math.min(minDifference, difference);
    }
}