soo 문제집 그리디 easy 문제 중 68문제를 풀었고, 그중 힌트를 참고한 문제 및 정리하기 위해 해당 글을 작성합니다.

문제번호	제목	난이도
1817번	짐 챙기는 숌	실버 5
20937번	떡국	실버 4
1499번	수리공 항승	실버 3
2872번	우리집엔 도서관이 있어	실버 1

1817번 짐 챙기는 숌

해결코드:

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        if(n > 0){
            st = new StringTokenizer(br.readLine());
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            int count = 1;
            int now = 0;
            for (int i = 0; i < n; i++) {
                if(now + arr[i] > m){
                    now = arr[i];
                    count++;
                }else{
                    now += arr[i];
                }
            }
            bw.write(count+"");
        }else{


            bw.write("0");
        }





        br.close();
        bw.close();
    }
}

해결 키포인트:

1. 차례대로 넣는 것이기 때문에 정렬하면 안된다
2. 또한 차례대로 넣는 것을때 최대 무게이기 때문에 그리디하게 풀면된다

고민/풀이흐름:

1. n이 0일 경우 입력이 없으므로 그냥 0을 출력한다
2. n이 0이 아닐 경우 이제 입력을 받는다
3. 먼저 개수를 세어주는 count는 1로 선언한다. 일단 하나의 박스에는 무조건 책을 넣을 것이기 때문이다.
4. 현재 무게를 누적해서 m과 비교하는 방식으로 판단한다
5. 만약 now + 현재 책의 무게가 m보다 크면 now에 현재 책의 무게를 넣고 count++한다
6. 아닐 경우 그냥 now에 넣으면된다
7. 이렇게 n만큼 순회한 뒤 count를 출력하면 정답이 된다.

링크:

1817번 - 짐 챙기는 숌

20937번 떡국

해결코드:

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

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int count = 1;
        Arrays.sort(arr);
        int ans = 1;
        for (int i = 1; i < n; i++) {
            if(arr[i] == arr[i-1]){
                count++;
                ans = Math.max(ans, count);
            }else{
                count = 1;
            }
        }


        bw.write(ans+"");
        br.close();
        bw.close();
    }



}

해결 키포인트:

1. 같은 크기의 위에는 쌓을 수 없고 무조건 작은 것만 쌓을 수 있다는 것을 명심하자
2. 얼핏보면 내림차순으로 정렬하면 되겠다고 생각할 수 있는데, 오름차순으로 정렬한뒤 같은 것의 개수를 세는 것이 키포인트이다.

고민/풀이흐름:

1. 먼저 각 입력값들에 대해서 오름차순 정렬을 해준다
2. count와 ans는 모두 1로 초기화한다. 떡국 탑은 무조건 최소 1개 이상은 나오기 때문이다
3. 두번째 값부터 이전값과 비교를 하는데 만약 같으면 count++해주고 정답에 ans와 비교해서 더 큰 값을 넣어준다
4. 만약 아닐 경우 count는 1로 초기화한다
5. 이렇게 같은 크기를 찾아줘야 하는 이유는 같은 크기는 같은 탑이 아닌 다른 탑이 될 수밖에 없기 때문이다
6. 또한 같은 크기가 여러개 있을 수도 있기 때문에, count로 그 개수를 누적해서 얼마나 같은 크기가 연속적으로 있는지 파악해야한다
7. 이렇게 누적해서 파악했을 때, 가장 같은 크기의 연속수가 많은 경우가 최소 탑의 개수가 된다
8. 파악한 ans를 출력하면 정답이 된다.

링크:

20937번 - 떡국

1499번 수리공 항승

해결코드:

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int l = 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());
        }

        Arrays.sort(arr);

        int range = (int) (arr[0] - 0.5 + l);
        int ans = 1;
        for (int i = 1; i < n; i++) {
            if(range < (int)(arr[i]+0.5)){
                range = (int)(arr[i]- 0.5 + l);
                ans++;
            }
        }

        bw.write(ans+"");

        br.close();
        bw.close();
    }



}

해결 키포인트:

1. 여기서 테이프는 그 위치의 좌우 0.5만큼 간격을 줘야한다를 꼭 이해야한다
2. 범위를 비교하고 누적하여, 그 개수를 파악하는 것이 키포인트다
3. 또한 2번을 위해서는 꼭 오름차순 정렬을 해주어야 한다

고민/풀이흐름:

1. 오름차순 정렬 후, 처음 위치에서 테이프를 붙였을 때, 가능한 범위를 찾는다
2. 첫번째 위치에서 0.5를 뺀뒤 l만큼을 더한 것이 가능한 범위이다
3. 만약 배열의 값이 범위보다 크다면 시작 위치를 다시 해당 위치에서 0.5빼고 l만큼 더한 범위로 갱신하고 개수를 늘려준다
4. 이렇게 늘렸을 때의 개수를 출력하면 정답이 된다
5. 참고로 무조건 하나의 테이프는 필요하므로 ans는 1로 초기화한다.

링크:

1499번 - 수리공 항승

2872번 우리집엔 도서관이 있어

해결코드:

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

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        int pivot = n;
        for (int i = n-1; i >= 0; i--) {
            if(pivot == arr[i]){
                pivot--;
            }
        }
        bw.write(pivot+"");

        br.close();
        bw.close();
    }
}

해결 키포인트:

1. 직접 정렬할 필요 없이 큰값 -> 작은값 순으로 내려갔을 때, 다른 값의 개수만 보는 것이 키포인트이다.

고민/풀이흐름:

1. 기준 변수 pivot을 n으로 초기화하고 뒤에서부터 비교한다
2. 만약 현재 배열의 값과 pivot이 같다면 pivot의 값을 내려준다
3. 이제 pivot을 순회 종료 후에 출력한다
4. pivot의 역할은 현재 찾는 값의 역할을 하면서도 정렬 안된 개수를 판단하는 역할이다

링크:

2872번 - 우리집엔 도서관이 있어