Solve001

문제번호: 11047(동전 0)

• 문제링크
• 깃허브

풀이

1. 동전을 오름차순으로 입력하기 때문에 따로 정렬할 필요는 없다
2. 가장 큰 동전부터 탐색을 하며 K보다 작을 시에 해당 동전이 K원을 만들 수 있는 가장 큰 동전이다.
3. 입력 K원이 0원이 될때까지 빼주며 K보다 작은 동전이 발견될 시에 계속 cnt를 1씩 증가시킨다.

import java.util.Scanner;

class Main {
    public static void main(String[] args){
        Scanner stdin = new Scanner(System.in);
        
        int n = stdin.nextInt();
        int k = stdin.nextInt();
        int cnt = 0;
        
        int[] coin = new int[n];
        
        for(int i = 0; i < n; i++){
            coin[i] = stdin.nextInt();
        }
        
        for(int j = n - 1; j >= 0; j--){
            while(true){
                if(k >= coin[j]){
                    k -= coin[j];
                    cnt++;
                }
                else
                    break;
            }
        }
        System.out.print(cnt);
    }
}

문제번호: 1914(하노이 탑)

• 문제링크
• 깃허브

풀이(시간초과)

1. 재귀를 이용하여 풀이 N-1개의 원판을 첫번째에서 중간 기둥으로 옮긴다
2. 첫번째 기둥 맨아래 원판은 세번째 기둥으로 옮긴다.
3. 재귀를 이용하여 중간 기둥으로 옮겼던 N-1개의 원판을 세번째 기둥으로 옮긴다.

• 재귀
  • 원판이 2개일 시, 위에서 한개를 하나의 그룹으로 본다.
  • 원판이 3개일 시, 위에서 두개를 하나의 그룹으로 보면 위에서 두개를 옮기는 방법을 이용
  • 원판이 4개일 시, 위에서 세개를 하나의 그룹으로 보면 위에서 세개를 옮기는 방법을 이용

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

public class boj_1914 {
    static int cnt = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        hanoi(N, 1, 3);
        System.out.println(cnt);
        if(N <= 20) {
            hanoi_print(N, 1, 3);
        }
    }

    static void hanoi(int n, int x, int y){
        if(n > 1){
            hanoi(n-1, x, 6 - x - y);
        }
        cnt += 1;
        if(n > 1){
            hanoi(n-1, 6 - x - y, y);
        }
    }
    static void hanoi_print(int n, int x, int y){
        if(n > 1){
            hanoi_print(n-1, x, 6 - x - y);
        }
        System.out.printf("%d %d\n",x, y);
        if(n > 1){
            hanoi_print(n-1, 6 - x - y, y);
        }
    }
}

• cnt = 2^N - 1인데 N을 100까지 표현하려면 시간초과가 뜬다.
• BigInteger를 이용해서 cnt 값을 출력한다.

풀이수정

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

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());
        BigInteger cnt = new BigInteger("2");
        cnt = cnt.pow(N);
        cnt = cnt.subtract(BigInteger.ONE);
        System.out.println(cnt);
        if(N <= 20) {
            hanoi_print(N, 1, 3);
        }
    }


    static void hanoi_print(int n, int x, int y){
        if(n > 1){
            hanoi_print(n-1, x, 6 - x - y);
        }
        System.out.println(x + " " + y);
        if(n > 1){
            hanoi_print(n-1, 6 - x - y, y);
        }
    }
}

문제번호: 1449(수리공 항승)

• 문제링크
• 깃허브

풀이

1. 구멍의 개수와 테이프의 길이를 입력한다.
2. 처음에 구멍의 개수에 맞게 테이프 칠을 하도록 cnt를 올린다.
3. 그 다음 테이프의 길이와 구멍 사이의 길이를 체크
   1. 구멍을 먼저 오름차순으로 정렬 Arrays.sort()
   2. 그 다음 가장 첫 구멍을 값에 저장한 다음, 뒤에 있는 값들과 비교
   3. 뒤 구멍 - 앞 구멍 + 1이 테이프의 길이보다 짧으면 cnt 1을 빼준다. (테이프 하나로 막을 수 있으므로)
   4. 그 다음 뒤에있는 구멍과도 비교를 해서 그 길이가 테이프 길이보다 크다면 index를 해당 구멍부터 시작하도록 옮겨준다.

import java.util.Arrays;
import java.util.Scanner;

import static java.lang.Math.abs;

public class boj_1449{
    public static Scanner stdin = new Scanner(System.in);
    static int cnt;

    public static void main(String[] args){
        int n = stdin.nextInt();
        int l = stdin.nextInt();

        int[] hole = new int[n];
        for(int i = 0; i < n; i++){
            hole[i] = stdin.nextInt();
        }

        System.out.println(solution(hole, l));

    }
    static int solution(int[] hole, int l) {
        Arrays.sort(hole);
        int a = hole[0];
        cnt = hole.length;

        for(int i = 1; i < hole.length; i++){
            if((abs(a - hole[i]) + 1 <= l)){
                cnt--;
            }
            else {
                a = hole[i];
            }
        }
        return cnt;
    }
}

문제번호: 1080(행렬)

• 문제링크
• 깃허브

풀이

1. 3x3의 행렬을 한꺼번에 뒤집기 때문에 만약 크기가 6x6인 행렬이라면 index 0 ~ 3 을 확인하고 4부터는 확인할 필요가 없다.
2. 따라서 index 0 ~ index N - 3 까지만 확인을 해주면 된다.
3. index 0 ~ index N - 3 에서 행렬a와 행렬b의 값이 다르면 해당 인덱스로부터 3x3 만큼 reverse 한다.
4. reverse 과정이 끝난 후에 행렬a와 행렬b가 동일한지 확인을 해야한다.
   • 6x6에서 index 0 ~ 3까지 확인하고 reverse를 수행한 후에, index 4와 index 5가 행렬끼리 서로 다르다면 이 연산으로는 같은 행렬이 될 수 없음을 의미한다.

public class Main {
    static int n;
    static int m;
    static int cnt = 0;
    static int[][] a;
    static int[][] b;

    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);

        n = stdin.nextInt();
        m = stdin.nextInt();

        a = new int[n][m];
        b = new int[n][m];

        for (int i = 0; i < n; i++) {
            String str = stdin.next();
            for (int j = 0; j < m; j++) {
                a[i][j] = str.charAt(j) - '0';
            }
        }
        for (int i = 0; i < n; i++) {
            String str = stdin.next();
            for (int j = 0; j < m; j++) {
                b[i][j] = str.charAt(j) - '0';
            }
        }
        System.out.println(solution());
    }

    static void reverse(int x, int y) {
        for (int i = x; i < x + 3; i++) {
            for (int j = y; j < y + 3; j++) {
                if (a[i][j] == 1) {
                    a[i][j] = 0;
                }
                else {
                    a[i][j] = 1;
                }

            }
        }
    }

    static int solution(){
        for (int i = 0; i < n - 2; i++) {
            for (int j = 0; j < m - 2; j++) {
                if (a[i][j] != b[i][j]) {
                    reverse(i, j);
                    cnt++;
                }
            }
        }
        for (int i = 0 ; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] != b[i][j]) {
                    return -1;
                }
            }
        }

        return cnt;
    }
}

문제번호: 1174(줄어드는 숫자)

• 문제링크
• 깃허브

Arraylist, collection 공부하기

풀이

• 최고로 큰 줄어드는 숫자인 987654321은 2^N-1번째 이므로 index 1024부터는 -1을 출력
• 987654321은 int타입으로는 표현할 수 없기 때문에 long타입 사용

1. 0 ~ 9 는 줄어드는 숫자이므로 0 ~ 9로 시작하며 재귀를 이용한다
2. 만약 solution(5, 1, list)가 실행된다면 list에 5, 50, 51, 510, 52, 520, 521, 5210, 53, 530, 531, 5310, 532, 5320, 5321, 53210 ...... 이 재귀적으로 계속 추가된다
   • 일의자리 수보다 작은 숫자들이 뒤로 계속 붙게됨
3. 자릿수가 10자리가 되면 list를 리턴한다
4. 현재 list에 존재하는 요소들은 정렬되지 않는 상태이므로 정렬시킨다.
5. 0이 제일 가장 작은 첫번째 줄어드는 숫자이므로 0번 index에 0이 저장되어 있으므로 1번 인덱스부터 출력되게 한다.

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

        int T = Integer.parseInt(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();

        for(int num = 0; num < 10; num++) {
            solution(num, 1, list);
        }
        Collections.sort(list);

        if(T > 1023){
            System.out.println(-1);
        }
        else {
            System.out.println(list.get(T - 1));
        }
    }

    static ArrayList solution(long num, int digit, ArrayList list){
        if(digit > 10){
            return list;
        }
        list.add(num);
        for(int i = 0; i < 10; i++){
            if(num % 10 > i){
                solution(num * 10 + i, digit + 1, list);
            }
        }
        return list;
    }
}

문제번호: 1105(팔)

• 문제링크
• 깃허브

풀이

1. 자리수가 커지면 무조건 0이 된다.
   • 자리수가 커질때 생기는 100, 1000, 10000 은 8이 없으므로
2. 두개의 수를 큰자리수부터 비교하며 같은지 확인한다.
   • 자리수의 숫자가 모두 다르거나 8이 없으면 8이 없어도 되므로 그냥 0이다.
3. 해당 자리수의 숫자가 다르면 중단한다.
   • 예를들어 819와 830라고 할때, 1과 3은 다르므로 자리수가 바뀔때(820) 8이 존재하지 않을 수 있다.
4. 해당 자리수의 숫자가 같으면 그 숫자가 8인지 확인하고 8이면 cnt 하나 올린다.
   • 예를들어 820과 835라고 할때, 앞자리 8은 바뀔 수 없고 2, 3은 830이 나올 수 있으므로 stop

public class Main {
    static int cnt = 0;

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

        System.out.println(solution(x, y));
    }
    static int solution(String x, String y){
        if(x.length() == y.length()) {
            for (int i = 0; i < x.length(); i++) {
                if(x.charAt(i) == y.charAt(i)){
                    if(x.charAt(i) == '8'){
                        cnt++;
                    }
                }
                else
                    break;
            }
        }
        return cnt;
    }
}

문제번호: 1092(배)

• 문제링크
• 깃허브

풀이

1. 배가 옮길 수 있는 무게, 박스의 무게를 역순으로 정렬한다.
2. 가장 큰 박스를 가장 큰 배에 못 실으면 -1 반환
3. 가장 큰 박스부터 가장 큰 배부터 싣는다.
4. 박스 idx, 배 idx 두 가지를 이용한다.
   • 만약 박스의 무게가 배보다 크면 박스 idx를 하나씩 늘려가면서 실을 수 있는지 확인
5. 배에 모두 실으면 cnt를 1올리고 다시 idx들을 초기화하고 실행
6. box에 요소가 다 없어지면 cnt 반환

public class Main {
    static ArrayList<Integer> box = new ArrayList<Integer>();
    static ArrayList<Integer> ship = new ArrayList<Integer>();
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int shipcnt = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < shipcnt; i++) {
            ship.add(Integer.parseInt(st.nextToken()));
        }
        int boxcnt = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < boxcnt; i++) {
            box.add(Integer.parseInt(st.nextToken()));
        }

        System.out.println(solution(shipcnt));

    }

    static int solution(int s) {
        Collections.sort(box);
        Collections.sort(ship);
        Collections.reverse(box);
        Collections.reverse(ship);

        if (box.get(0) > ship.get(0)) {
            return -1;
        }
        while (!box.isEmpty()) {
            int ship_idx = 0;
            int box_idx = 0;
            while (ship_idx < s) {
                if (ship.get(ship_idx) >= box.get(box_idx)) {
                    box.remove(box_idx);
                    ship_idx++;
                }
                else if (ship.get(ship_idx) < box.get(box_idx)) {
                    box_idx++;
                }
                if(box_idx == box.size()){
                    break;
                }
            }
            cnt++;
        }
        return cnt;
    }
}

문제번호: 1946(신입사원)

• 문제링크
• 깃허브

풀이

1. 시간 복잡도를 줄이기 위해 서류심사 성적을 오름차순으로 정렬을 한다.
   • (정렬 하는법 제대로 공부하기)
2. 서류심사의 성적이 정렬이 된 상태이기 때문에 2등 부터는 1등의 면접심사 등수보다 높아야 한다.
3. 최소값 변수를 하나 선언하고 1등의 면접심사 등수를 대입한다.(기준값)
4. 2등부터 면접심사 등수를 체크한다
   • 만약 최소값에 저장되어 있는 면접심사 등수보다 높다면 최솟값을 해당 등수 면접심사 등수로 바꾼다.
     • 뒤에 있는 등수 사람들은 서류심사 등수가 낮기때문에 면접은 무조건 높아야 한다. 따라서 최소값보다 항상 커야함.
   • 만약 최소값에 저장되어 있는 면접심사 등수보다 낮다면 해당 인원은 채용되지 않기 때문에 전체 인원에서 1감소

public class Main {
    static ArrayList<point> arr;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            arr = new ArrayList<point>();
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                arr.add(new point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }
            System.out.println(solution(n));
        }
    }
    static int solution(int n){
        Collections.sort(arr, new Comparator<point>() {
            @Override
            public int compare(point o1, point o2) {
                return o1.x > o2.x ? 1 : -1;
            }
        });
        int cnt = arr.size();
        int min = arr.get(0).y;
        for(int i = 1; i < n; i++){
            if(min < arr.get(i).y){
                cnt--;
            }
            else
                min = arr.get(i).y;
        }

        return cnt;
    }
}
class point{
    int x;
    int y;

    public point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

문제번호: 1263(시간관리)

• 문제링크
• 깃허브

풀이

1. 일단 가장 우선적으로 처리해야 할일부터 정렬한다.
2. 정렬 후에 임의의 i번 idx에서 끝내는 시간이 x_time이라면 0 ~ i까지의 인덱스들의 걸리는 시간의 합이 x_time을 넘어서는 안된다.
   • 넘는다면 애초에 해당 idx일은 할 수가 없는 일.
3. 가장 처음 해야할일의 걸리는 시간이 y_time 이라면 y_time까지 반복문을 돌려준다.
   • 여기서 2의 조건에 위배되는 사항이 있으면 -1을 반환한다.
   • 그렇지 않다면 해당 반복문의 idx가 답이된다.

• 중첩 반복문 나올때 flag를 이용하자.

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Time> arr = new ArrayList<Time>();
    static int time = 0;
        public static void main(String[] args) throws IOException {
            int n = Integer.parseInt(br.readLine());
            for(int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                arr.add(new Time(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }
            System.out.println(solution(n));
        }

        static int solution(int n){
            Collections.sort(arr, new Comparator<Time>() {
                @Override
                public int compare(Time o1, Time o2) {
                    return o1.si > o2.si ? 1 : -1;
                }
            });

            boolean flag = false;
            for(int i = 0; i <= arr.get(0).si; i++){
                int idx = 0;
                int sum = i;
                while(idx < n) {
                    sum += arr.get(idx).ti;
                    if (sum > arr.get(idx).si){
                        if(i == 0){
                            return -1;
                        }
                        flag = true;
                        break;
                    }
                    idx++;
                }
                if(flag == true){
                    break;
                }

                time = i;
            }
            return time;
        }
}

class Time{
    int ti;
    int si;

    public Time(int ti, int si){
        this.ti = ti;
        this.si = si;
    }
}

문제번호: 1068(트리)

• 문제링크
• 깃허브

풀이

• DFS, BFS 공부
• DFS 풀때 배열 선언 예시.

ArrayList<Integer>[] tree = new ArrayList[개수];

1. 입력 받은 개수만큼 ArrayList 선언하고, 각각에 인덱스마다 인접노드를 저장한다.
   • 양방향 입력

       - tree[i].add(parent);
       - tree[parent].add(i);

2. 재귀를 이용하여 DFS 방식으로 트리를 순회하며, 삭제 노드를 순회할 때 재귀 stop.
   • 마지막 leaf를 순회하게 되면 count 하나씩 증가시킨다.

• 실수 한 부분: index[0]이 무조건 root가 되는게 아님.

public class boj_1068 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Integer>[] tree;
    static boolean[] isvisited;
    static int leaf_cnt = 0;
    static int root = 0;
    static int delete_idx = 0;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        isvisited = new boolean[n];
        tree = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            tree[i] = new ArrayList<Integer>();
            isvisited[i] = false;
        }
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; i++){
            int parent = Integer.parseInt(st.nextToken());

            if(parent != -1) {
                tree[i].add(parent);
                tree[parent].add(i);
            }
            else root = i;
        }
        delete_idx = Integer.parseInt(br.readLine());

        if(delete_idx == root){
            System.out.println(0);
        }
        else{
            DFS(root);
            System.out.println(leaf_cnt);
        }
    }

    static void DFS(int node){
        isvisited[node] = true;
        boolean haschild = false;
        for(int i = 0; i < tree[node].size(); i++){
            if(tree[node].get(i) != delete_idx && !isvisited[tree[node].get(i)]) {
                haschild = true;
                DFS(tree[node].get(i));
            }
        }
        if(!haschild){
            leaf_cnt++;
        }
    }


}