[알고리즘] 그리디 풀이 - 1

Kevin·2025년 2월 22일
백준 자바 13305백준 자바 16953백준 자바 1715백준 자바 1789백준 자바 2217

Algorithm

목록 보기
2/10
post-thumbnail

Just win or learn

1. 로프

정답

import java.io.*;
import java.util.Arrays;

public class Main {

    public void solution() 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 max = 0;

        Integer[] arr = new Integer[n];

        for (int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        for (int i = 0; i < n; i++) {

            if ((arr[i] * (n - i)) > max) {
                max = arr[i] * (n - i);
            }
        }

        bw.write(max + "\n");

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

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

최대 중량이 가장 작은 로프를 사용하게 되면 N개로 등분을 할 수 있게 되어 가장 많은 무게를 등분하게 될 가능성이 크다.

그게 아니라 작은 로프를 사용하지 않다고 하면 그만큼의 등분을 못하게 된다.

10과 15의 중량을 감당할 수 있는 2개의 로프가 있을 때

만약 10의 중량을 감당할 수 있는 로프를 사용하게 되면 2개의 로프로 감당할 수 있다.

그러나 15의 중량을 감당할 수 있는 로프를 사용하게 되면 10의 중량을 로프는 감당할 수 없기에 1개의 로프로 감당 해야만 한다.

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


2. 수들의 합

정답

import java.io.*;

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long n = Long.parseLong(br.readLine());
        long ans = 0;
        long i = 1;

        while (true) {
            if ((n - ans) < i) break;

            ans += i;
            i++;
        }

        bw.write(i - 1 + "\n");

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

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

나의 경우에는 처음에 시간 초과가 났다.

그 이유는 숫자의 범위를 확인 하지 못하고, int 형으로 변수들을 선언했기 때문이었다.

이를 통해서 long으로 타입을 변경 하여 시간 초과를 해결 하였다.

배운 점

  • 문제에서 주어진 변수의 범위를 잘 살펴보자.

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


3. 주유소

틀린 답(17점 코드)

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

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

        long ans = 0;
        boolean isFind = false;

        long[] distanceArr = new long[n-1]; // 거리 배열
        long[] costArr = new long[n]; // 비용 배열

        for (int i=0; i < n - 1; i++) {
            distanceArr[i] = Long.parseLong(st.nextToken());
        }

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

        for (int i=0; i < n; i++) {
            costArr[i] = Long.parseLong(st.nextToken());
        }

        long[] costSortArr = Arrays.copyOfRange(costArr, 1, n - 1); // 맨 앞 인덱스와 맨 뒤 인덱스를 제외한 정렬에 사용될 배열

        Arrays.sort(costSortArr); // 최소 금액을 찾기 위한 정렬

        for (int i=0; i < n - 1; i++) {
            if (!isFind && costArr[i] != costSortArr[0]) { // 현재 도시가 최저 금액이 아니라면 일단 다음 도시까지 갈 정도만 기름을 넣어야 한다.
                ans += costArr[i] * distanceArr[i];
            }

            if (isFind || costArr[i] == costSortArr[0]) { // 만약 현재 도시가 최저 금액이면, 맨 오른쪽 까지 갈 기름을 여기서 넣어야한다.
                isFind = true;
                ans += costSortArr[0] * distanceArr[i];
            }
        }

        bw.write(ans + "\n");

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

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

나는 무조건적으로 최소값을 찾고, 해당 최소 가격에서 남은 거리를 모두 계산 해버린다는 전제가 있었다.

그러나 위 전제는 아래의 반례가 있다.

4
2 2 2
2 4 1 2

위 도시 중 가장 가격이 저렴한 곳은 1이다.

이를 위 로직을 통해 계산하면 14라는 값이 나오지만 정답은 10이다.

첫 도시에서 2원에 4L를 주유하고, 세번째 도시에서 1원에 2L를 주유 하면 10원이 나온다.

해당 반례를 통해 알 수 있는 것은 현재 도시의 주유소보다 싼 주유소가 앞에 있다면 최소 금액의 주유소가 아니더라도 그걸 사용하는게 이득일 수 있다.

이를 통해 알 수 있는 것은 한번에 최소 금액만을 찾아서 순회 하는게 아니라 앞 뒤 도시의 금액을 비교 하여 매번 최소값을 갱신하며 이를 계산 해 나가면 된다.

위 반례를 통해서 예를 들면 다음과 같다.

2 4 1 2

위의 숫자는 각 도시의 기름 가격이다.

2는 4보다 작다. 그렇기에 첫번째 도시에서 기름을 넣어 세번째 도시까지 간다.

2는 1보다 작다. 그렇기에 세번째 도시에서 기름을 넣어 네번째 도시까지 간다.

즉 내림차순 이 적용될 때 최소값을 교체 해주면서 거리를 계산 해주면 된다.

그렇게 하면 자연스럽게 최적의 값을 찾아가게 된다.

정답

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

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

        long ans = 0;

        long[] distanceArr = new long[n-1]; // 거리 배열
        long[] costArr = new long[n]; // 비용 배열

        for (int i=0; i < n - 1; i++) {
            distanceArr[i] = Long.parseLong(st.nextToken());
        }

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

        for (int i=0; i < n; i++) {
            costArr[i] = Long.parseLong(st.nextToken());
        }

        long minCost = costArr[0];

        for (int i=0; i < n - 1; i++) {
            if (costArr[i] < minCost) { // 최소 비용으로 갈 거리 주유
                minCost = costArr[i];
            }

            ans += minCost * distanceArr[i];
        }

        bw.write(ans + "\n");

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

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

배운 점

  • 정렬을 한 것이 단순히 정답이 아니면, 최소나 최대 변수를 선언 및 매번 비교 하여 값을 산출하자.
  • 반례들을 잘 확인하자.

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


4. 카드 정렬하기

틀린 답

import java.io.*;
import java.util.Arrays;

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        Integer[] arr = new Integer[n];
        Integer[] ansArr = new Integer[n];

        for (int i=0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr); // 가장 횟수가 적은 묶음을 찾는 오름차순

        int tmp = arr[0];
        int ans = 0;

        if (n == 1) {
            bw.write(tmp + "\n");
        } else {
            for (int i = 1; i < n; i++) {
                if (i == 1) {
                    tmp = arr[i] + tmp;
                    ansArr[0] = 0;
                    ansArr[1] = tmp;
                } else {
                    ansArr[i] = arr[i] + tmp;
                    tmp = arr[i] + tmp;
                }
            }
            for (int i=0; i < n; i++) {
                ans += ansArr[i];
                bw.write(ansArr[i] + "\n");
            }
            bw.write(ans + "\n");
        }

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

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

이번 문제의 패착은 다음과 같을 것 같다.

문제에 대한 명확한 이해가 동반 되지 않고, 주어진 케이스 맞춰서 문제를 구현 하다 보니 불 필요한 조건절이나 반복문이 많이 생겼다.

그러면서 반례나 주어진 케이스에 너무 몰입 되었던 것 같다.

문제를 푸면서는 오름차순 후 맨 첫번째 인덱스의 값이 ans에 포함 되지 않도록 하는 것에 포커스를 두었다.

예를 들어서 10, 20, 40 문제에서 오름차순 후 반복문을 돌면서, ans를 더할 때 첫번째 인덱스는 두 묶음의 카드 합이 아니기에 빼주려고 했다.

해당 문제를 알고리즘으로만 푸려고 했는데, 자료구조로 간단하게 풀 수 있는 방법을 깨달았다.

정답

해당 문제는 데이터의 삽입, 삭제, 정렬이 자주 일어나기에 우선순위 큐를 이용 해야 한다.

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {

    public void solution() 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 sum = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)

        for (int i=0; i<n; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }

        while(pq.size() > 1) {
            int first = pq.poll();
            int twice = pq.poll();
            sum = sum + first + twice;
            pq.add(first + twice);
        }

        bw.write(sum + "\n");

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

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

위의 코드를 통해서 카드를 두 묶음 형태로 더 해가면서, 그 더해진 값을 우선 순위 큐에 다시 넣어주면 된다.

이렇게 하면, 문제에서 요구한대로 두 묶음 형태로 자연스럽게 더해나갈 수 있다.

배운 부분

  • 반드시 수도 코드를 먼저 작성한 후 구현을 진행 해야 한다.
  • 알고리즘이 아닌 자료구조로 훨씬 간단하게 풀 수 있는 방법이 있다.
    • 문제가 주어지고 해결 방법을 깨달았을 때 이를 알고리즘으로 풀지, 자료구조로 풀지 고민 해봐야 한다.
  • 우선순위 큐에 대해서 알게 되었다.

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


5. A → B

틀린 답

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public void solution() 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 startNum = Integer.parseInt(st.nextToken());
        int endNum = Integer.parseInt(st.nextToken());
        int cnt = 0;

        while (true) {
            if (startNum == endNum) {
                break;
            }

            if (startNum > endNum) {
                cnt = -2;
                break;
            }

            if (endNum % 10 == 1) { // 마지막 자리 수 제거
                endNum /= 10;
                cnt += 1;
            }

            if (endNum % 2 != 0) {
                cnt = -2;
                break;
            }

            endNum /= 2;
            cnt += 1;

        }

        bw.write(cnt + 1 + "\n");

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

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

풀이 방법은 매우 간단하다.

B 부터 시작을 하여 맨 뒤의 숫자가 1로 끝나면 1을 떼주면 되고, 그게 아니면 2로 나누어주면 된다.

만약 이 때 1로 끝나지도 않고, 2로 나누어지지도 않는다면 -1을 반환하면 된다.

이 때 틀렸다는 답이 나왔는데 나는 내 풀이가 맞다는 확신이 있었다.

그래서 질문 게시판의 반례들을 모두 대입 해봤는데 정상적인 값이 출력 되었다.

정답

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public void solution() 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 startNum = Integer.parseInt(st.nextToken());
        int endNum = Integer.parseInt(st.nextToken());
        int cnt = 1;

        while (startNum != endNum) {

            if (startNum > endNum) {
                cnt = -1;
                break;
            }

            if (endNum % 10 == 1) {
                endNum /= 10;
                cnt += 1;
            } else if (endNum % 2 == 0) {
                endNum /= 2;
                cnt += 1;
            } else {
                cnt = -1;
                break;
            }
        }

        bw.write(cnt + "\n");

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

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

문제의 풀이는 전반적으로 같다.

대신 반복문이나 조건절의 조건에 대해서 변경점을 부여 하였다.

배운 부분

  • 내 풀이 방법이 맞다는 확신이 있는데, 틀리는 경우에는 반복문 조건이나 조건절의 조건에 빈틈이 없었나 살펴볼 필요가 있다.
  • 되도록 알고리즘 문제에서는 빈틈이 없게 할 수 있도록 if - else if - else 문을 사용하자.

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

profile
Kevin
Hello, World! \n
이전 포스트

[알고리즘] 그리디 알고리즘

다음 포스트

[알고리즘] 그리디 풀이 - 2

0개의 댓글