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

 

2003번: 수들의 합 2

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

www.acmicpc.net

 

[난이도]

- 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 출력

'코딩테스트' 카테고리의 다른 글

백준 2606: 바이러스[JAVA]  (0) 2024.04.25
백준 26876: New Time[JAVA]  (0) 2024.04.24
16173 점프와 쩰리  (0) 2024.04.24
6186 Best Grass  (1) 2024.04.24
백준 17198: Bucket Brigade[JAVA]  (0) 2024.04.24

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

 

17198번: Bucket Brigade

The input file contains 10 rows each with 10 characters, describing the layout of the farm. There are exactly one barn, one lake, and one rock.

www.acmicpc.net

[난이도]

- 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까지 도착했을 때의 소의 개수를 알 수가 있다.

'코딩테스트' 카테고리의 다른 글

16173 점프와 쩰리  (0) 2024.04.24
6186 Best Grass  (1) 2024.04.24
백준 1065: 한수[JAVA]  (0) 2024.04.17
백준 4673: 셀프 넘버[JAVA]  (0) 2024.04.17
백준 14501: 퇴사[JAVA]  (0) 2024.04.17

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

 

4673번: 셀프 넘버

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때,

www.acmicpc.net

 

 

[난이도]

- 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을 넘어갈 경우 반복문 탈출 후 출력

'코딩테스트' 카테고리의 다른 글

백준 17198: Bucket Brigade[JAVA]  (0) 2024.04.24
백준 1065: 한수[JAVA]  (0) 2024.04.17
백준 14501: 퇴사[JAVA]  (0) 2024.04.17
백준 9290: 틱택토 이기기[JAVA]  (0) 2024.04.16
백준 5568: 카드 놓기[JAVA]  (0) 2024.04.14

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

 

1639번: 행운의 티켓

첫째 줄에 문자열 S가 주어진다. 문자열 S는 1보다 크거나 같고, 9보다 작거나 같은 수로만 이루어져 있고, 길이는 50보다 작거나 같은 자연수이다.

www.acmicpc.net

 

[난이도]

- 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

 

1544번: 사이클 단어

사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에

www.acmicpc.net

 

 

[난이도]

- 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

 

1018번: 체스판 다시 칠하기

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

[난이도]

- 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)) 로 찾는다. 그리고 원래 알고있는 최솟값과 새로찾은 최소값을 비교해 정답을 찾는다.

 

 

'코딩테스트' 카테고리의 다른 글

백준 1544: 사이클 단어[JAVA]  (0) 2024.04.12
백준 7568: 덩치[JAVA]  (0) 2024.04.12
백준 2057: 팩토리얼 분해[JAVA]  (0) 2024.04.10
백준 1476: 날짜 계산[JAVA]  (0) 2024.04.09
백준 1543: 문서 검색[JAVA]  (0) 2024.04.09

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

 

2057번: 팩토리얼 분해

음 아닌 정수 N이 주어졌을 때, 이 수를 서로 다른 정수 M(M ≥ 1)개의 팩토리얼의 합으로 나타낼 수 있는지 알아내는 프로그램을 작성하시오. 예를 들어 2=0!+1!로 나타낼 수 있지만, 5는 이와 같은

www.acmicpc.net

 

[레벨]

- 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를 출력한다.

 

'코딩테스트' 카테고리의 다른 글

백준 7568: 덩치[JAVA]  (0) 2024.04.12
백준 1018: 체스판 다시 칠하기[JAVA]  (0) 2024.04.11
백준 1476: 날짜 계산[JAVA]  (0) 2024.04.09
백준 1543: 문서 검색[JAVA]  (0) 2024.04.09
백준 1436: 영화감독 숌[JAVA]  (0) 2024.04.09

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

 

1476번: 날짜 계산

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타

www.acmicpc.net

 

 

[난이도]

- 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를 반환한다.

 

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

+ Recent posts