<stdio.han>

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

[정답 코드]

import java.io.*;
import java.math.BigInteger;
import java.util.*;

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

        int N = Integer.parseInt(st.nextToken());
        BigInteger[] dist = new BigInteger[N - 1]; // 거리 배열
        BigInteger[] cost = new BigInteger[N]; // 비용 배열

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N - 1; i++) {
            dist[i] = new BigInteger(st.nextToken()); // 거리 배열 입력
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            cost[i] = new BigInteger(st.nextToken()); // 비용 배열 입력
        }

        BigInteger total = BigInteger.ZERO; // 총 주유 비용
        BigInteger min = cost[0]; // 가장 싼 기름 값
        for (int i = 0; i < N-1; i++) {
            if (min.compareTo(cost[i]) > 0) { // 왼쪽값이 오른쪽 값보다 크면 1, 같으면 0, 작으면 -1
                min = cost[i]; // 현재 가장 싼 기름 값 보다 더 싼 곳이 있을경우 갱신
            }
            total = total.add(min.multiply(dist[i])); // 가야할 거리 * 현재 가장 싼 기름값
        }
        System.out.println(total); // 출력
    }
}

[설명]

이 문제는 그리디 알고리즘 문제이다. 처음 문제를 봤을때는 쉬워 보이지만 아이디어가 잘 생각나지 않아 구글링을해 다른사람들의 아이디어를 참고했다. 

기본적인 아이디어는 현재 알고있는 기름값 보다 더 싼 비용의 기름값을 만날때 까지 충전해 길을 가는것이다.

예를들면 노드가 8 9 9 5 6 2 4 4 5 1 1 이런식으로 되어있다면 시작지점에서 가장 싼 기름값은 1리터당 8원이다. 그다음 노드의 비용응 9이므로 그다음 싼 기름값인 지점인 5노드까지 8원 인 노드에서 한번에 충전해서 가는것이다. 그 다음 더 싼 비용의 노드를 만나면 그때 가장 싼 기름값을 갱신시켜 그보다 싼 비용의 노드를 만날때 까지 가는것이다. 

쉽게 보자면 8 9 9 5 6 2 4 4 5 1 1 이 아닌 8 8 8 5 5 2 2 2 2 1 1 이렇게 볼 수 있다. 코드에 주석이 달려 있으니 확인해보면 좋다.

중요한 점이 하나 더 있다. 바로 BigInteger를 사용하는 것이다. 이 문제는 매우 큰 수를 사용하기 때문에 int로는 정답을 도출해 낼 수 없다.

BigInteger total 에 0이 담겨야한다. 이 때 total = 0이 아닌 BigInteger.ZERO 로 0을 담을 수 있다.

BigInteger 끼리의 대수 비교를 할 때 단순 부등호를 활용해 비교하는것이 아닌. BigInteger1.compareTo(BigInteger2) 를 활용해야 한다. 이때 왼쪽에 적은 BigInteger1이 오른쪽에 적은 BigInteger보다 크다면 1, 같으면 0, 작다면 -1이 출력된다.

그래서 현재 알고있는 가장 싼 기름값 보다 새로 알게된 기름값이 더 싸다면 1이 출력되 if문이 true가 되어 가장 싼 기름값을 갱신해준다.

마지막에 가야할거리*기름값을 계산할때 total = total + ( min * dist[i] )가 아닌 BigInteger.add(BigInteger.multiply(BigInteger) 형식으로 계산을 해주어야 한다.

결론적으로 이 문제는 그리디 + BigInteger의 활용하는 문제였다.

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

[정답 코드]

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

public class Main {
    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(), " ");

        int T = Integer.parseInt(st.nextToken()); // T개의 테스트 케이스
        int[] answer = new int[T]; // 한번에 출력하기 위한 answer 배열
        for (int i = 0; i < T; i++) { // T번의 반복
            st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int[] ranks = new int[N]; // N등까지 존재함
            Map<Integer, Integer> countMap = new HashMap<>();
            st = new StringTokenizer(br.readLine(), " ");
            int max = Integer.MIN_VALUE;
            for (int j = 0; j < N; j++) {
                int data = Integer.parseInt(st.nextToken());
                countMap.put(data, countMap.getOrDefault(data, 0) + 1); // 해당팀의 인원이 6명되는지 체크
                ranks[j] = data; // 각 등수의 팀
                max = Math.max(max, data); // 가장 큰 번호의 팀
            }

            int[] fifthPlayer = new int[max + 1]; // 해당 팀의 5번째 선수
            Map<Integer, Integer> scoreMap = new HashMap<>();
            Map<Integer, Integer> tmpMap = new HashMap<>();
            int score = 1;

            for (int rank : ranks) {
                if (countMap.get(rank) == 6) { // 팀원이 6명 모두 통과한 팀만
                    tmpMap.put(rank, tmpMap.getOrDefault(rank, 0) + 1);

                    if (tmpMap.get(rank) <= 4) { // 해당팀의 4등까지만 점수를 기록함
                        scoreMap.put(rank, scoreMap.getOrDefault(rank, 0) + score);
                    }

                    if (tmpMap.get(rank) == 5) { // 해당 팀의 5번째 선수의 점수
                        fifthPlayer[rank] = score;
                    }

                    score++;

                }
            }
            int result = Integer.MAX_VALUE;
            int fifthScore = Integer.MAX_VALUE;
            for (Integer key : scoreMap.keySet()) {
                int tmp = scoreMap.get(key);
                if (tmp < result) { // 점수가 가장 낮은팀이 우승
                    result = tmp;
                    fifthScore = fifthPlayer[key];
                    answer[i] = key;
                } else if (tmp == result) { // 점수가 동점일 경우 5번째 선수의 점수가 낮을 경우 우승
                    if (fifthScore > fifthPlayer[key]) {
                        answer[i] = key;
                    }
                }
            }
        }
        for (int i : answer) {
            System.out.println(i); // 출력
        }
    }
}

[설명]

이 문제는 구현 문제이다. 그런데 문제가 어려워서 그런건지 백준의 질문게시판에도 질문도 없고 답변도 없고 구글링에도 자료가 많이 부족하다. 그래서 푸는데 많이 어려움을 겪었다. map.getOrDefault()를 사용해 맵에 값이 없을 경우 default 값을 넣어주는 함수를 활용한게 코드를 많이 줄일수있었다.

백준 2468번: 안전 영역[JAVA]

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

[정답 코드]

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

public class Main {
    static int N,result, count, nx, ny;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1}; // 상하좌우 4방탐색
    static int[] dy = {1, -1, 0, 0};
    static ArrayList<Integer> list = new ArrayList<>();
    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(), " ");


        // graph 초기화
        N = Integer.parseInt(st.nextToken());
        graph = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());

                // 건물의 높이들이 담긴 리스트
                if (!list.contains(graph[i][j])) { // 중복체크
                    list.add(graph[i][j]);
                }
            }
        }

        result = 1;
        for (Integer height : list) { // 0부터 끝까지 탐색하는것은 비효율적이기 때문에 리스트 활용
            count = 0;
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && graph[i][j] >= height) {
                        count++;
                        dfs(height, i, j);
                    }
                }
            }
            result = Math.max(result, count); // 새로탐색한결과 중에 더 큰값 저장
        }
        System.out.println(result);
    }

    static void dfs(int height, int x, int y) {
        visited[x][y] = true;
        // 4방탐색
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N) { // 그래프 범위 안에 있을 경우
                if (!visited[nx][ny]) { // 방문하지 않은 건물인 경우
                    if (graph[nx][ny] >= height) { // 그 건물이 물의 높이보다 높을 경우
                        dfs(height, nx, ny);  // 상하좌우 인접한 건물을 찾는다
                    }
                }
            }
        }
    }

}

[설명]

이 문제는 완전탐색 알고리즘이다. 그중 dfs 알고리즘을 활용해 문제를 해결했다. dx/dy 기법을 활용한 4방 탐색도 활용했다. 먼저 2차원 배열을 선언해준다. 이 때 중요한점이 입력값들을 중복값을 체크하며 리스트에 담아놔야한다. 그렇지 않을 경우는 비의 양을 0부터 끝까지 중복탐색해야해서 메모리 초과가 나거나 비효율적이다. 

dfs 로직은 4방탐색을 하며 그 범위가 방문하지않은 건물이며 그 건물이 물의 높이 보다 높을경우 dfs를 다시 실행한다. 

그 후 결과값을 비교해 최대값을 출력한다.

백준 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. 결과값이 조건을 통과할 경우 출력한다.

백준 1699번: 제곱수의 합[JAVA]

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

[정답 코드]

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

public class Main {
    static int N;
    static int[] dp;
    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());
        dp = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            dp[i] = i;
            for (int j = 1; j * j <= i; j++) {
                if (dp[i] > dp[i - j * j] + 1) {
                    dp[i] = dp[i - j * j] + 1;
                }
            }
        }
        System.out.println(dp[N]);

    }
}

[설명]

dp[1]  =  1  => 1^2

dp[2]  =  2  => 1^2 + 1^2

dp[3]  =  3  => 1^2 + 1^2 + 1^2

dp[4]  =  1  => 2^2

dp[5]  =  2  => 1^2 + 2^2

dp[6]  =  3  => 1^2 + 1^2 + 2^2

dp[7]  =  4  => 1^2 + 1^2 + 1^2 + 2^2

dp[8]  =  2  => 2^2 + 2^2

dp[9]  =  1  => 3^2

dp[10]  =  2  => 1^2 + 3^2

dp[1] , dp[4], dp[9], dp[16] 같이 어떤 수의 제곱인 수는 제곱수가 1개 있다. 그 점을 이용해 N 에서 dp[1] , dp[4], dp[9] ... 을 뺀 후 1을 더해 구한다. 1을 더하는 이유는 dp[1] , dp[4], dp[9] ... 가 1을 대신하기 때문이다.

예를 들어 15는

(15 - 1) 의 최소 제곱수의 합 + 1   // 1 = 1^1
(15 - 4)의 최소 제곱수의 합 + 1   // 4 = 2^2
(15 - 9)의 최소 제곱수의 합 + 1  /  9 = 3^3
중 가장 작은 값이다.

백준 15649번: N과 M[JAVA]

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

[정답 코드]

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

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

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];
        visit = new boolean[N]; // 기본값 모두 false

        dfs(0);

        System.out.println(sb);
        br.close();
    }

    public static void dfs(int depth) {
        if (depth == M) {
            //depth 가 M까지 도착하면 sb에 집어넣고 return
            for (int i : arr) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true; // 방문한 노드는 true
                arr[depth] = i + 1;
                dfs(depth + 1);
                visit[i] = false; // 탐색이 모두 끝나면 모두 false 로 변경
            }
        }
    }
}

[설명]

위 그림을 보면 이해하기가 쉽다. 

입력값으로 3 3 을 입력받아 자연수 1부터 3(N) 까지의 수를 3(M)개 고른것이다.

M개를 골라야하기 때문에 배열 int[M] 을 선언한 후 DFS를 하며 찾아가는것이다.

백준 9663번: N-Queen[JAVA]

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

[정답코드]

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

public class Main {
    static int N;
    static int[] arr;
    static int count = 0;

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

        N = Integer.parseInt(st.nextToken());
        arr = new int[N];

        dfs(0);
        System.out.println(count);

        br.close();
    }

    public static void dfs(int depth) {
        if (depth == N) {
            //depth가 N까지 도착하면 return
            count++;
            return;
        }
        for (int i = 0; i < N; i++) {
            arr[depth] = i;
            if (possible(depth)) {
                // 모든 조건에 통과하면 다음 depth탐색
                dfs(depth + 1);
            }
        }
    }

    public static boolean possible(int col) {
        for (int i = 0; i < col; i++) {
            // 같은 행인지
            if (arr[i] == arr[col]) {
                return false;
            }
            //대각선방향에 존재하는지
            else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
                return false;
            }
        }
        // 같은행에도 없고 대각선방향에도 없으면 true
        return true;
    }
}

[설명]

N-Queen 문제는 대표적인 백트래킹 알고리즘 문제이다. 체스룰을 안다면 알수있듯이 퀸은 상하좌우,대각선방향으로 움질일 수 있다. 문제에서는 서로 공격할 수 없는 경우의 수 이기 때문에 각 퀸들이 같은행, 같은열에 존재하지 않고 해당 위치에서 대각선방향에 존재해서는 안된다.

dfs, 백트래킹 알고리즘으로 풀 수 있다.

[그림 해석]

먼저 1행1열에 퀸을 놓는다. 그 다음 depth로 간다. 2번째 퀸은 2행1열에 놓지만 같은열에 존재하기 때문에 바로 탐색을 종료한다. 다시 2번째 퀸을 2행2열에 놓아본다. 이번엔 대각선에 위치하기 때문에 탐색을 종료한다. 이번엔 2행3열에 놓아보니 놓을 수 있는 위치이다. 다음 depth로 이동한다. 이를 반복하다 정답을 찾을경우 return 한다.

간단히 설명하자면

정답을 찾기위해 depth++ 하며 탐색을 하고, 정답이 아닐경우 다시 돌아온다.