<stdio.han>

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

[난이도]

- Silver 4

[알고리즘]

- 부르트 포스

[코드]

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

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int answer = 0;
        for (int i = 0; i < N; i++) {
            int sum = arr[i];
            int j=i;
            while (sum <= M) {
                if (sum == M) { // sum 이 N이 될경우 정답을 1 증가
                    answer++;
                    break;
                }
                j++;
                if (j >= N) { // j가 arr 인덱스를 넘어갈 경우 break
                    break;
                }
                sum+=arr[j];
            }
        }
        System.out.println(answer);
    }
}

[풀이]

1.i=0부터 arr[i] + arr[i+1] +... + arr[j-1] + arr[j] 를 구한다.

2. arr[i] + arr[i+1] +... + arr[j-1] + arr[j] 가 M일경우 i를 1 증가시키고 answer를 1증가시킨다.

3. answer 출력

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

[난이도]

- Silver 4

[알고리즘]

- bfs

[코드]

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

public class Main {
    static char[][] graph = new char[10][10];
    static boolean[][] visited = new boolean[10][10];
    static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dy = {0, 0, -1, 1}; // 상, 하, 좌, 우
    static Queue<int[]> queue = new LinkedList<>();
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        for (int i = 0; i < 10; i++) {
            String input = br.readLine();
            for (int j = 0; j < 10; j++) {
                graph[i][j] = input.charAt(j);
                if (graph[i][j] == 'L') {
                    queue.add(new int[]{i, j, 0});
                    visited[i][j] = true;
                }
            }
        }

        bfs();
        System.out.println(answer - 1); // B 제외하고 출력해줘야함


    }

    static void bfs() {
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int cows = tmp[2];
            if (graph[x][y] == 'B') {
                answer = Math.min(answer, cows);
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < 10 && ny >= 0 && ny < 10) { // graph 내부안에서만 가능
                    if (!visited[nx][ny]) { // 방문하지 않은 지역
                        if (graph[nx][ny] != 'R') { // 돌이 있을 경우 돌아가야함
                            visited[nx][ny] = true; // 방문한곳으로 표시
                            queue.add(new int[]{nx, ny, cows + 1}); // 소의 개수를 1씩 늘림
                        }
                    }
                }
            }
        }
    }
}

[풀이]

Queue에 x와 y의 좌표뿐만아니라 소의 개수를 1씩 늘리면서 큐에담아주어야 B까지 도착했을 때의 소의 개수를 알 수가 있다.

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

[난이도]

- Silver 5

[알고리즘]

- 부르트 포스

[코드]

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

public class Main {
    static boolean[] check = new boolean[10036];// selfNumber(9999) = 9999+9+9+9+9=10035가 최대값

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

        int n = 1;
        while (n <= 10000) {
            if (!check[n]) {
                bw.write(n + "\n");
            }
            selfNumber(n);
            n++;
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static void selfNumber(int n) {
        int sum = 0;
        sum += n;
        String str = String.valueOf(n);
        for (int i = 0; i < str.length(); i++) {
            sum += str.charAt(i) - '0';
        }
        check[sum] = true;
    }
}

[풀이]

1. 1부터 시작해 check[n] 이 false일 경우 해당 숫자를 출력한다. check[n] 이 true일 경우에는 출력하지 않는다.

2. selfNumber(n)을 수행후 나온결과의 값을 sum이라 할 때, check[sum] = true  해준다.

3. n이 10000을 넘어갈 경우 반복문 탈출 후 출력

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

[난이도]

- Silver 4

[알고리즘]

- 구현

- 부르트 포스

[코드]

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));

        String S = br.readLine();

        int N = 0;
        int answer = 0;
        for (int i = 1; i <= S.length() / 2; i++) { // (S의 길이 / 2)만큼 반복
            N = i * 2; // N은 2의배수로 증가함
            for (int j = 0; j < S.length() - N + 1; j++) { // (S의 길이 - N + 1)만큼 반복
                String tmp = S.substring(j, j + N); // 문자열을 j부터 j+N 만큼만 추출
                if (StringSum(tmp.substring(0, N / 2)) == StringSum(tmp.substring(N / 2))) { // 각 자리수를 더한 값이 같다면 true
                    answer = N; // answer 는 현재 확인하는 문자열의 길이 N
                    break; // 이미 answer를 찾았다면 더이상 할 필요가 없기 때문에 break;
                }
            }
        }
        System.out.println(answer);

        br.close();
    }

    static int StringSum(String s) { // 각 자리수를 더한 값을 반환
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            sum += s.charAt(i) - '0';
        }
        return sum;
    }
}

[풀이]

부르트 포스 문제인줄알고 풀었지만 풀다보니 그냥 구현문제 같다. break로 반복문을 탈출하기 때문에 부르트포스 같지 않다.

1. 입력받은 (문자열의 길이 / 2) 만큼 반복한다. 문자열을 2N만큼 잘라서 확인하기 때문에 이렇게 제한을 두지 않으면 인덱스를 넘어가 오류가 발생한다.

2. 문자열을 2N만큼 잘라서 확인 후 좌, 우를 나눠 각 자리수의 합을 구한다. 좌, 우의 합이 같을 경우 answer을 N으로 초기화해준다.

다 풀고보니 시작을 2부터시작해 2, 4, 6, 8 ... 이런식으로 하는것보다 큰 수부터 ... 8, 6, 4, 2 이렇게 푸는게 시간이 더 적게 걸릴것 같다.

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

[난이도]

- Silver 4

[알고리즘]

- 부르트 포스

[정답 코드]

import org.w3c.dom.html.HTMLParagraphElement;

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 N = Integer.parseInt(st.nextToken());

        List<String> list = new ArrayList<>();
        
        for (int i = 0; i < N; i++) {
            list.add(br.readLine());
        }

        for (int i = 0; i < N; i++) {
            String tmp1 = list.get(i);
            for (int j = i + 1; j < N; j++) {
                if (tmp1.length() == list.get(j).length()) {
                    String tmp2 = list.get(j) + list.get(j);
                    if (tmp2.contains(tmp1)) {
                        list.remove(j);
                        N--;
                        j--;
                    }
                }
            }
        }
        System.out.println(N);

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

[풀이]

예를들어 turepic이라는 단어를 2번연속 적으면 turepicturepic 이라는 단어가 만들어 지는데, 이 문자열안에 picture라는 단어가 존재하는지 검사하는 방법을 사용했다. 

1. 배열이 아닌 ArrsyList에 입력값을 받아준다.

2. 검사할 단어와 비교하려는 단어의 길이가 같다면 검사를 해준다.

3. 검사 결과 사이클 단어가 맞다면 비교한 단어를 list에서 제거해준다.

• 그냥 제거해주면 list의 인덱스가 한칸씩 밀리기 때문에 j--도 같이 해준다.
• list를 하나 지운것이기 때문에 N--도 해준다. N--를 하지않는다면 list 인덱스밖을 검사하려고 시도하기 때문에 오류가 발생한다. 

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

[난이도]

- Silver 4

[알고리즘]

- 부르트 포스

[정답 코드]

import org.w3c.dom.html.HTMLParagraphElement;

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

public class Main {
    static char[][] arr;
    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());
        int M = Integer.parseInt(st.nextToken());

        arr = new char[N][M];

        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = input.charAt(j);
            }
        }

        int answer = Integer.MAX_VALUE;
        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                answer = Math.min(answer, Math.min(startWhite(i, j), startBlack(i, j)));
            }
        }
        System.out.println(answer);

    }

    static int startWhite(int x, int y) {
        int sum = 0;
        for (int i = x; i < x+8; i++) {
            for (int j = y; j < y+8; j++) {
                if (i % 2 == 0 && j % 2 == 0) {
                    if (arr[i][j] != 'W') {
                        sum++;
                    }
                } else if (i % 2 != 0 && j % 2 == 0) {
                    if (arr[i][j] != 'B') {
                        sum++;
                    }
                } else if (i % 2 == 0 && j % 2 != 0) {
                    if (arr[i][j] != 'B') {
                        sum++;
                    }
                } else {
                    if (arr[i][j] != 'W') {
                        sum++;
                    }
                }
            }
        }

        return sum;
    }

    static int startBlack(int x, int y) {
        int sum = 0;
        for (int i = x; i < x+8; i++) {
            for (int j = y; j < y+8; j++) {
                if (i % 2 == 0 && j % 2 == 0) {
                    if (arr[i][j] != 'B') {
                        sum++;
                    }
                } else if (i % 2 != 0 && j % 2 == 0) {
                    if (arr[i][j] != 'W') {
                        sum++;
                    }
                } else if (i % 2 == 0 && j % 2 != 0) {
                    if (arr[i][j] != 'W') {
                        sum++;
                    }
                } else {
                    if (arr[i][j] != 'B') {
                        sum++;
                    }
                }
            }
        }

        return sum;
    }
}

[풀이]

처음엔 2차원 그래프가 나오고 문제흐름상 dfs나 bfs와 4방탐색을 활용하면 풀 수 있겠다! 라고생각했었다. 그런데 풀다보니 그렇게 풀면 코드가 더 짧아지고 시간이 더 짧게 걸릴수는 있겠지만 진짜 부르트하게 풀어도 풀리겠는데? 라는생각이 들어 다른방식으로 풀었다.

1. 입력받은 값중 나올 수 있는 보드판들의 시작위치를 i, j로 설정한다.

2. 시작위치가 W로 시작할 때와 B로 시작할 때 두가지 경우를 모두 확인해주어야 한다.

3. 각 말이 놓여야 하는 색과 다른색이 있을경우 sum을 1씩 증가시켜 새로칠하는 경우만 체크해준 후 반환해준다.

4. 두값중에 더 작은값을 Math.min(startWhite(i, j), startBlack(i, j)) 로 찾는다. 그리고 원래 알고있는 최솟값과 새로찾은 최소값을 비교해 정답을 찾는다.

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

[레벨]

- Silver 5

[알고리즘]

- 부르트 포스

- 수학

[정답 코드]

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));

        long N = Long.parseLong(br.readLine());
        long[] arr = new long[21];
        if (N == 0) {
            System.out.println("NO");
            return;
        }

        arr[0] = 1L;
        for (int i = 1; i <= 20; i++) {
            arr[i] = arr[i-1] * i;
        }

        for (int i = 20; i >= 0; i--) {
            if (N >= arr[i]) {
                N -= arr[i];
            }
        }

        if (N == 0) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

[풀이]

N의 범위가 20! 까지이기 때문에 전체적으로 long 으로 초기화해준다.

N이 0일 경우 바로 NO를 출력해준다.

1. N을 20! 부터 0!까지 차례로 빼본다.

2. N >= arr[i]일 경우 N-=arr[i]을 한다.

3. 반복 후 N이 0일 경우 YES 아닐경우 NO를 출력한다.

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

[난이도]

- Silver 5

[알고리즘]

- 부르트 포스

- 수학

[정답 코드]

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));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int E = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int e = 1, s = 1, m = 1;
        int answer = 1;

        while (true) {
            if (e == E && s == S && m == M) {
                break;
            }
            answer++;
            e++;
            if (e > 15) {
                e=1;
            }
            s++;
            if (s > 28) {
                s=1;
            }
            m++;
            if (m > 19) {
                m=1;
            }
        }
        System.out.println(answer);

    }
}

[풀이]

1. e = 1, s = 1, m = 1로 초기화 해준다.

2. e++, s++, m++을 하면서 e==E, s==S, m==M이 될때 까지 반복한다.

3. e는 15를 넘어갈 경우 1로 돌아온다. s는 28을 넘어갈 경우 1로 돌아온다. m은 19를 넘어갈 경우 1로 돌아온다.

4. answer를 반환한다.

좀더 수학적으로 스마트하게 풀 수 있는 방법이 있을것 같은데 내 머리로는 불가능 했다.