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://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());
    }

}

문제

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

공부한 부분

최초 생각 : 해시에다가 일단 넣고, 스택에다가 넣은거 빼면서 비교하자
1. 해시셋에 입력, 이때 스택에도 같이 넣어줌 (스택 사용해서 문자 연속으로 나오는것 확인을 위해)

2. 스택에서 알파벳을 한개씩 빼서 이전의 알파벳과 같은지 검사해서 다른 경우의 개수를 세어준다.

3. 이때의 개수가 해시셋에 있는 개수와 같으면 그룹단어

Java Code

package week2;

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

public class boj1316 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //해시에다가 일단 넣고, 스택에다가 넣은거 빼면서 비교?

        int answer = 0;
        for (int i = 0; i < N; i++) {

            st = new StringTokenizer(br.readLine());

            String input = st.nextToken();
            char[] arr = input.toCharArray();
            HashSet<Character> hs = new HashSet();
            Stack<Character> stack = new Stack<>();

            for (int j = 0; j < arr.length; j++) {
                hs.add(arr[j]);
                stack.push(arr[j]);
            }

            char temp1 = stack.pop();
            int count = 0;

            while (!stack.isEmpty()){

                char temp2 = stack.pop();
                if (temp1 != temp2) {
                    count++;
                    //System.out.println("count "+count);
                }
                temp1 = temp2;
            }

            if (count == hs.size()-1) {
                answer++;
            }


        }
        System.out.println(answer);
    }
}

문제

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

공부한 부분

2차원 배열일 때 구간합 구하는 법에 대해 공부했다.

1. 2차원 구간 합 배열 D[X][Y] 정의

D[X][Y] = 원본 배열의 (0,0)부터 (X,Y)까지의 사각형 영역 안에 있는 수의 합

2. D[i][j]의 값을 채우는 구간 합 공식

D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]

3. 질의 X1,Y1,X2,Y2에 대한 답을 구간합으로 구하는 방법

D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]

Java Code

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

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[][] map = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[][] sum = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + map[i][j];
            }
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int X1 = Integer.parseInt(st.nextToken());
            int Y1 = Integer.parseInt(st.nextToken());
            int X2 = Integer.parseInt(st.nextToken());
            int Y2 = Integer.parseInt(st.nextToken());
      
            int answer = sum[X2][Y2] - sum[X1 - 1][Y2] - sum[X2][Y1 - 1] + sum[X1 - 1][Y1 - 1];
            System.out.println(answer);
        }
    }
}

문제

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

공부한 부분

구간합 구하는 법에 대해 공부했다.

1. 합 배열을 구한다.

S[i] = S[i-1]+A[i]

2. 구간 합을 구한다.

구간합 = S[j] - S[i]

Java Code

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

public class boj_003_11659 {
    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[] num = new int[N+1];
        int sum = 0;
        int[] sumArr = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
            sum += num[i];
            sumArr[i] = sum;
        }
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            System.out.println(sumArr[B]-sumArr[A-1]);

        }
    }
}

문제

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

풀이

방법1. 

처음에는 입력을 받으면서 최대값을 구하고,

입력된 모든 값을 점수/M*100으로 고치면서 총합을 구해서 평균을 구했는데 이렇게 되면 for문을 2번 돌게 된다.

방법2.

어차피 (A/M*100+B/M*100+C/M*100)/3 = (A+B+C)/M*100 이니까 for문 한번에 해줄 수 있었다. (2번째 방법)

Java Code (방법1)

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

public class boj_002_1546 {
    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());
        double[] score = new double[N];
        double max = Double.MIN_VALUE;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < score.length; i++) {
            score[i] = Double.valueOf(st.nextToken());
            max = Math.max(score[i],max);
        }
        double sum = 0.0;
        double[] changedScore = new double[N];
        for (int i = 0; i < score.length; i++) {
            changedScore[i] = score[i]/max*100;
            sum +=changedScore[i];
        }

        System.out.println(sum/N);
    }
}

Java Code (방법2)

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

public class boj_002_1546_2 {
    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());
        double[] score = new double[N];
        double max = Double.MIN_VALUE;
        double sum = 0.0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < score.length; i++) {
            score[i] = Double.valueOf(st.nextToken());
            max = Math.max(score[i],max);
            sum += score[i];
        }
        double answer = sum/max*100/N;


        System.out.println(answer);
    }
}

문제

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

N개의 숫자가 공백 없이 쓰여있을 때, 숫자의 합을 출력하는 문제

공부한 부분

1. 공백 없이 숫자가 주어질 때 입력 값 받는 방법

12345 이런식으로 입력이 주어지고, 1,2,3,4,5 숫자를 따로 사용해야 할 때

일단 String 값으로 12345를 받고, char형 배열에 toCharArray를 사용해서 분리해준 후

해당 char형 값에 -'0' 해주어 int 값으로 바꿔준다.

숫자 CHAR(0~9)는 ASCII 코드 48부터 시작하므로, 48을 빼주면 숫자를 얻을 수 있다.

char c = '5';
int n = 0;
n = c - 48;

char c = '5';
int n = 0;
n = c - '0';

Code

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

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

        int N = Integer.parseInt(br.readLine());
        String sNum = br.readLine();
        char[] cNum = sNum.toCharArray();

        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += cNum[i]-'0';
        }
        System.out.println(sum);
    }
}