leeso

문제

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

공부한 부분

그리디 알고리즘 : 각 단계별로 최선의 선택지를 선택하는 것.

그리디 알고리즘은 항상 최적의 해를 도출해내는 것은 아니다.

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj11047 {

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

        int[] coin = new int[N];
        for (int i = 0; i < N; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }
        int count = 0;
        for (int i = N -1; i>= 0; i--) {
            if(coin[i] <= K) {
                count += (K / coin[i]);
                K = K % coin[i];
            }
        }
        System.out.println(count);
    }
}

문제

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

공부한 부분

dp 관련 문제는 일단 dp[10] 정도까지는 써보면서 규칙을 확인해보면 좋을 것 같다.

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class boj12865 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];

        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = 100001;
            for (int j = 1; j <= i / 2; j++) {
                if (j * j == i) {
                    dp[i] = 1;
                    break;
                }
                dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
            }
        }
        System.out.println(dp[n]);
    }

}

문제

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

공부한 부분

숫자가 주어지고 각각 자리수의 합을 구하려고 할 때, %10이랑 /10 활용하면 좋다.

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class boj2231 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = 0;

        for (int i = 1; i <= N; i++) {
            int tmp = i;
            int sum = i;

            while (tmp > 0) {
                sum = sum + tmp % 10;
                tmp = tmp / 10;
            }
            if(sum == N) {
                M = i;
                break;
            }
        }
        System.out.println(M);
    }
}

문제

https://leetcode.com/problems/bulls-and-cows/

풀이

bulls : guess의 숫자가 secret의  올바른 위치에 있는 경우

cows : secret에 있는 숫자이지만 guess에서 잘못된 위치에 있는 경우

numsSecret==numsGuess 인 경우 bulls를 ++

정확하게 일치하는 경우 외에,

secret에 있는 숫자인 경우 -- 해주고, guess에 있는 숫자인 경우 ++ 해준다.

그 이후 배열의 숫자를 확인해서

numsGuess에 있는게 -인 경우 cows++해주고, numsSecret에 있는게 +인 경우 cows++ 해준다.

Java Code

class Solution {
    public String getHint(String secret, String guess) {
        int bulls=0;
        int cows=0;
        int[] nums=new int[10];
        for(int i=0;i<secret.length();i++){
            int numsSecret=secret.charAt(i)-'0';
            int numsGuess=guess.charAt(i)-'0';
            if(numsSecret==numsGuess){
                bulls++;
            }else{
                if(nums[numsGuess]<0){
                    cows++;
                }
                if(nums[numsSecret]>0){
                    cows++;
                }
                nums[numsGuess]++;
                nums[numsSecret]--;
            }
            
        }
        return bulls + "A" + cows + "B";
    }
}

문제

https://leetcode.com/problems/backspace-string-compare/

풀이

s문자를 배열로 바꿔서 stack 활용해서 문자 만들어주고,

t문자를 배열로 바꿔서 같은 방법으로 해줘서 결과 비교해서 return 해준다.

Java Code

import java.util.Stack;

class Solution {
    public boolean backspaceCompare(String s, String t) {
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != '#') {
                stack.push(arr[i]);
            } else if(!stack.isEmpty()){
                stack.pop();
            }
        }
        String str1 = stack.toString();
        stack.clear();
        char[] arr1 = t.toCharArray();
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != '#') {
                stack.push(arr1[i]);
            } else if(!stack.isEmpty()){
                stack.pop();
            }
        }
        String str2 = stack.toString();
        if (str1.equals(str2)) {
            return true;
        } else {
            return false;
        }
    }
}

문제

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

풀이

dfs탐색으로 모든 경우의 수를 탐색해준다

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj1189 {

    static int R, C, K;
    static char[][] map;
    static int[][] visited;
    static int answer;

    static int[] moveR = {1, -1, 0, 0};
    static int[] moveC = {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());
        K = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        visited = new int[R][C];

        for (int i = 0; i < R; i++) {
            String s = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = s.charAt(j);
            }
        }

        visited[R - 1][0] = 1;
        dfs(R - 1, 0, 1);

        System.out.println(answer);

    }

    static void dfs(int r, int c, int moved) {
        if (r == 0 && c == C - 1) {
            if (moved == K) {
                answer++;
            }
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextR = r + moveR[i];
            int nextC = c + moveC[i];
            if (nextR < 0 || nextR >= R || nextC < 0 || nextC >= C) {
                continue;
            }
            if (visited[nextR][nextC] == 1 || map[nextR][nextC] == 'T') {
                continue;
            }
            visited[nextR][nextC] = 1;
            dfs(nextR, nextC, moved + 1);
            visited[nextR][nextC] = 0;

        }

    }

}

문제

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

풀이

큐를 사용하면 되겠다!

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }

        while (queue.size() > 1) {
            queue.remove();
            if(queue.isEmpty()) break;
            int top = queue.poll();
            queue.add(top);
        }
        System.out.println(queue.peek());
    }

}