<stdio.han>

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

[난이도]

- 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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String before = br.readLine();
        String after = br.readLine();
        int beforeMin = Integer.parseInt(before.substring(3));
        int afterMin = Integer.parseInt(after.substring(3));
        int beforeHour = Integer.parseInt(before.substring(0, 2));
        int afterHour = Integer.parseInt(after.substring(0, 2));

        int answer = 0;
        while (beforeMin != afterMin) {
            beforeMin++;
            answer++;
            if (beforeMin == 60) {
                beforeMin -= 60;
                beforeHour++;
                if (beforeHour == 24) {
                    beforeHour-=24;
                }
            }
        }
        while (beforeHour != afterHour) {
            beforeHour++;
            answer++;
            if (beforeHour == 24) {
                beforeHour-=24;
            }
        }
        System.out.println(answer);

    }
}

[풀이]

bfs 알고리즘으로 풀어야하는데 어떻게 푸는지도 모르겠고 부르트 포스로 풀어버렸다.

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/16173

[난이도]

- Silver 4

[알고리즘]

- bfs

[코드]

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

public class Main {
    static int N;
    static int[] dx = {1, 0}; // 아래, 오른쪽
    static int[] dy = {0, 1}; // 아래, 오른쪽
    static int[][] graph;
    static boolean[][] visited;
    static Queue<int[]> queue = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        graph = new int[N][N];
        visited = new boolean[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());
            }
        }
        queue.add(new int[]{0, 0});
        visited[0][0] = true;

        bfs();

    }
    static void bfs() {
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            if (graph[x][y] == -1) {
                System.out.println("HaruHaru");
                return;
            }
            for (int i = 0; i < 2; i++) {
                int nx = x + dx[i] * graph[x][y];
                int ny = y + dy[i] * graph[x][y];
                if (nx < N && ny < N && !visited[nx][ny]) { // graph 범위 내라면
                    queue.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
        System.out.println("Hing");
    }
}

[풀이]

이동은 아래 혹은 오른쪽으로 밖에 이동하지 못하기 때문에 처음에는 방문한지역을 체크하는 visited 배열을 사용하지 않았었다. 하지만 게임판의 숫자는 0이상 100이하여서 0이 적혀있을 경우 제자리를 계속 방문하게 되어 메모리 초과가 발생하기 때문에 이를 해결하기위해 visited 배열을 추가했다.

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

[난이도]

- Silver 4

[알고리즘]

- bfs

[코드]

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

public class Main {
    static int R, C;
    static char[][] graph;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dy = {0, 0, -1, 1}; // 상, 하, 좌, 우
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        graph = new char[R][C];
        visited = new boolean[R][C];
        int answer = 0;

        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++) {
                graph[i][j] = input.charAt(j);
            }
        }
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (graph[i][j] == '#') { // if graph[i][j] is grass
                    if (!visited[i][j]) {
                        bfs(i, j);
                        answer++;
                    }
                }
            }
        }
        System.out.println(answer);
    }

    static void bfs(int r, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r, c});
        visited[r][c] = true;
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < R && ny >= 0 && ny < C) { // if 'nx' and 'ny' are inside of map
                    if (!visited[nx][ny]) { // and have never visited
                        if (graph[nx][ny] == '#') {
                            visited[nx][ny] = true; // turn visited[nx][ny] true
                            queue.add(new int[]{nx, ny}); // add queue
                        }
                    }
                }
            }
        }
    }
}

[풀이]

1. Using a double for loop, we check if graph[i][j] represents grass and has not been visited before. If so, we perform bfs(i, j).

2. Upon visiting, we mark the location as visited by setting it to true and explore adjacent grass patches using the 4-directional search logic.

3. Finally, we print the numbber of grass clumps.

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/1065

[난이도]

- 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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        if (N < 100) {
            System.out.println(N);
        } else {
            int answer = 99;
            for (int i = 100; i <= N; i++) {
                int hundreds = i / 100; // 100의 자리
                int tens = (i / 10) % 10; // 10의 자리
                int units = (i % 10); // 1의 자리
                if ((hundreds - tens) == (tens - units)) {
                    answer++;
                }
            }
            System.out.println(answer);
        }
    }
}

[풀이]

N이 99이하일 경우에는 모든 수가 등차수열을 이룬다.

N이 100이상일 경우에는 (100의 자리 - 10의 자리) == (10의 자리 1의 자리) 일 경우에 등차수열을 이룬다 라고 말할 수 있다.

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/14501

[난이도]

- Silver 3

[알고리즘]

- 부르트 포스

- dfs

[코드]

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

public class Main {
    static int N, maxPay = Integer.MIN_VALUE;
    static int[][] arr;
    static boolean[] checked;
    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;

        N = Integer.parseInt(br.readLine());

        arr = new int[N][2];
        checked = new boolean[N];

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

        dfs(0, 0);
        System.out.println(maxPay);

    }

    static void dfs(int index, int pay) {
        if (index >= N) {
            maxPay = Math.max(maxPay, pay);
            return;
        }

        if (index + arr[index][0] <= N) { // 날짜를 초과하지 않는다면
            dfs(index + arr[index][0], pay + arr[index][1]); // 상담을 진행 후의 날짜, 금액을 추가해 넘겨준다
        } else { // 날짜를 초과한다면
            dfs(index + arr[index][0], pay); // 금액을 추가하지않고 넘겨준다, 다음 if문에서 걸리기 때문
        }
        dfs(index + 1, pay); // 완전 탐색하기위한 코드, 0일부터시작, 1일부터 시작, ...
    }
}

[풀이]

1. index가 N을 초과할 경우 현재까지 쌓인 pay중의 최대값을 maxPay에 저장한다.

2 - 1. 현재날짜에서 상담 후의 날짜가 N을 초과하지 않는다면 (상담 후의 날짜, 상담 후의 금액)을 넘겨준다.

2 - 2. 현재날짜에서 상담 후의 날짜가 N을 초과한다면(상담 후의 날짜, 상담 전의 금액)을 넘겨준다. 이렇게 하는 이유는 다음 if문에서 걸려 maxPay를 갱신하기 위함이다.

3. 0일째부터 상담 시작했을 경우가 끝났다면, 다시 1일부터 상담 시작했을 경우, 2일부터 상담 시작했을 경우... 로 계속진행한다. N + 1일부터 상담 시작했을 경우까지 갔을 경우 끝난다.