개발자 Lim

문제 링크

분류

다이나믹 프로그래밍

문제 설명

스타로드와 토끼는 토르를 구출하기 위해서 우주선을 만들고 있다.

우주선을 만들기 위해서는 총 N개의 부품을 상점에서 모두 구입해야 한다. 모든 부품은 무게 W와 에너지 E를 갖고 있다. 상점에서는 모든 부품을 1부터 N번까지 부품을 순서대로 나열해놓고 판매하고 있다.

이 상점에서는 특이하게도 부품의 가격을 W*E의 비용으로 팔고 있다. 상점에서는 또한 특이한 방식의 판매를 하는데, L 부품부터 R 부품중 최대 무게 W_max 와 최대 에너지 E_max의 곱 W_max *E_max의 비용을 지불한다면 L부터 R사이의 모든 부품을 한번에 구입할 수 있다. 또한 이 상점은 X부품과 Y부품 (X<Y)을 동시에 구입하거나 X부품을 Y부품 보다 먼저 구입할 순 있지만, Y부품을 X부품보다 먼저 구입할 순 없다.

그렇다면 스타로드와 토끼가 모든 부품을 살 수 있는 최소의 비용을 구해보도록 하자.

입력

첫 번째 줄에는 부품의 개수 N(1 ≤ N ≤ 1,000)가 주어진다.

두 번째 줄에는 각 부품의 무게 W(0 ≤ W ≤ 1,000,000)가 주어진다.

세 번째 줄에는 각 부품의 에너지 E(0 ≤ E ≤ 1,000,000)가 주어진다.

출력

스타로드와 토끼가 모든 부품을 살 수 있는 최소비용을 한줄에 출력하라.

풀이1 (동적 프로그래밍 바텀 업)

시간 복잡도 O(n^3) 공간 복잡도 O(n)

아이디어: dp[n+1] 공간을 n번째 까지의 물품을 구매했을 때의 최소 비용을 저장하는 배열로 지정

특수한 방법으로 모든 물건을 한번에 구매하는 경우 vs (1~n-1)까지의 물품을 최소 비용으로 구매하는 경우 + 나머지 물품을 한번에 구매하는 경우 중 작은 값을 dp배열에 저장하게 하여 dp[n]을 구한다.

O(n)으로 할 수 없는 이유

단순하게 현재의 물건까지의 최소비용 dp[i-1] + 다음 물건을 단일 구매 비용 E*W vs 모든 물건 구매비용 MaxE*MaxW 라고 가정하여 문제에 접근 할 경우 (특수한 방법으로 한번에 구매, 단일 구매, 특수한 방법으로 한번에 구매) 하는 경우를 체크 할 수가 없기 때문에

5
10 9 1 7 6
4 2 99 4 3

해당 예제를 걸러낼 수 없게 된다. [10*4(1~2 구매) + 1*99(3 단일 구매) + 7*4(4~5 구매)]

결론은 추가적인 반복을 사용하여 이전 물품을 현재 물품과 특수한 방법으로 한번에 구매하는 경우들과 비교하여 비용을 최소값이 나오는 경우로 최신화 하여야한다. 

i = 5 일 경우 

(dp[1] + 9*99) vs (dp[2] + 7*99) vs (dp[3] + 7*4) vs (dp[4] + 6*3)

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

public class Main {
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static long stl(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[n+1];
        Arrays.fill(dp,Long.MAX_VALUE);
        int[] weights = new int[n+1];
        int[] energies = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) weights[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) energies[i] = Integer.parseInt(st.nextToken());
        dp[0] = 0;
        int maxWeight = 0; int maxEnergie=0;
        for (int i = 1; i <=n ; i++) {	
            long historySum = Long.MAX_VALUE;
            // 모든 물품을 한번에 구매하는 경우의 값을 구하기 위한 변수 선언 
            maxWeight = Math.max(maxWeight, weights[i]);
            maxEnergie = Math.max(maxEnergie, energies[i]);
            for (int j = 1; j < i; j++) {
            	// dp[5]를 채운다 가정하면 dp[1]~dp[4] + 나머지 물품들을 특수한 방법으로 구매하는 금액
                // 을 모두 체크하여 가장 작은 값을 dp[5]에 저장
                int tmpMaxWeight = 0;
                int tmpMaxEnergie = 0;
                // dp[j<i] + (j+1)~(i)까지의 물품을 한번에 구매하는 경우 체크 갱신
                for (int k = j+1; k <=i; k++) {
                    tmpMaxEnergie = Math.max(tmpMaxEnergie, energies[k]);
                    tmpMaxWeight = Math.max(tmpMaxWeight,weights[k]);
                }
                historySum = Math.min(historySum,dp[j] + (long) tmpMaxEnergie *tmpMaxWeight);
            }
            // 모든 물품을 한번에 구매하는 경우의 비용
            long specialSum = ((long) maxEnergie * maxWeight);
            dp[i] = Math.min(historySum, specialSum);
        }
        System.out.println(dp[n]);

    }
}

개선된 풀이2 (동적 프로그래밍 바텀 업)

시간 복잡도 O(n^2) 공간 복잡도 O(n)

각 부품에 대해 그 부품을 포함하는 서브셋에서의 최대 무게와 에너지를 찾아내는 방식 이전 방식과는 다르게 모든 부품을 한번에 고려하지 않고 매 반복시에 역순으로 돌아가서 n에 해당 하는 물품까지 구매했을 때 최소비용을 찾아내어 갱신하는 방식

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

public class Main {
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static long stl(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[n+1];
        Arrays.fill(dp, Long.MAX_VALUE);
        int[] weights = new int[n+1];
        int[] energies = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) weights[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) energies[i] = Integer.parseInt(st.nextToken());
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            int maxWeight = 0, maxEnergie = 0;
            for (int j = i; j >= 1; j--) {
                maxWeight = Math.max(maxWeight, weights[j]);
                maxEnergie = Math.max(maxEnergie, energies[j]);
                dp[i] = Math.min(dp[i], dp[j-1] + (long)maxWeight * maxEnergie);
            }
        }
        System.out.println(dp[n]);
    }
}

문제 링크

분류

다이나믹 프로그래밍

문제 설명

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이 (동적프로그래밍 - 바텀 업)

시간 복잡도 O(n) 공간 복잡도 O(n)

가치의 합에 대한 코인의 필요 갯수를 저장해두는 dp[] 배열을 사용해서 1~k까지의 반복을 통해 코인의 필요 갯수를 재갱신하여 풀었다.

j 원을 만들기위한 방법 = 기존에 갱신한 j원을 만드는데 필요한 동전의 수 vs j-n원을 만들기 위한 동전의 수 + n원 짜리 동전 하나

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

public class Main {
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static long stl(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }
    static final int INF = (int)10e9;

    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[] coins = new int[n+1];
        for(int i=1; i<=n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[k+1];
        Arrays.fill(dp, 100001);  // Impossible value
		// 0원을 만드는데 필요한 코인 수는 0개
        dp[0] = 0;
        for(int i=1; i<=n; i++) {
            for(int j=coins[i]; j<=k; j++) {
                dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1);
            }
        }

        if (dp[k] == 100001) {
            System.out.println(-1);
        } else {
            System.out.println(dp[k]);
        }
    }
}

문제 링크

분류

누적 합, 정렬, 스위핑

문제 설명

다각형의 두 선분이 연속하는 선분의 꼭짓점을 제외하고는 만나지 않는 다각형을 단순다각형이라고 부른다. 다각형의 각 변이 x축과 y축에 평행한 다각형을 직각다각형이라 부른다. 단순다각형이면서 직각다각형을 단순직각다각형이라 부른다. 아래 두 그림은 단순직각다각형의 예를 보여준다.

단순직각다각형이 주어질 때, 수평선 H가 다각형의 수직선분과 몇 번 교차하는지 또는 수직선 V가 다각형의 수평선분과 몇 번 교차하는지 알고자 한다. 첫 번째 그림에서 수평선 H는 4개의 수직선분과 교차하고 수직선 V는 2개의 수평선분과 교차한다. 두 번째 그림은 첫 번째 그림에서 수평선 H의 위치를 조금 위로 옮긴 것으로 8개의 수직선분과 교차하게 된다.

이때, 단순직각다각형과 가장 많이 교차하는 수평선 H와 수직선 V의 위치를 찾아 그때의 교차 횟수를 구하고자 한다. 단, 수평선 H는 다각형의 어떤 수평선분과도 겹처 놓여서는 안 되고, 유사하게 수직선 V는 다각형의 어떤 수직선분과도 겹쳐 놓여서는 안 된다.

수평선 H의 위치를 잘 정해서 주어진 단순직각다각형의 수직선분과 가장 많이 교차하는 지점을 찾을 때, 그 때의 교차 횟수를 h라 하고, 유사하게 수직선 V와 주어진 단순직각다각형의 수평선분과 가장 많이 교차하는 횟수를 v라 할 때, max(h, v)를 출력하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 n(4 ≤ n ≤ 100,000)이 주어지고, 이어지는 n개 줄 각각에 단순직각다각형 꼭지점의 좌표 (x_i, y_i)가 차례대로 주어진다. 주어지는 꼭지점들의 순서는 시계방향이다. 다각형의 꼭지점을 나타내는 각 좌표값은 정수이며, -500,000 ≤ x_i, y_i ≤ 500,000이다.

출력

max(h, v)를 출력한다.

실패한 풀이(구현 방식으로 풀이)

시간 복잡도 O(n^2) 공간 복잡도 O(n)

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

public class Main {
    public static class Pos{
        int start;
        int end;
        public Pos(int x,int y){
            this.start = x;
            this.end = y;
        }
    }
    public static int sti(StringTokenizer st) {
        return Integer.parseInt(st.nextToken());
    }

    public static long stl(StringTokenizer st) {
        return Long.parseLong(st.nextToken());
    }

    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;
        // 입력 받기
        int ans = 0;
        int n = Integer.parseInt(br.readLine()); // 첫 번째 줄의 숫자를 읽어서 n에 저장합니다.
        int[][] pairs = new int[n][2]; // n개의 쌍을 저장하기 위한 2차원 배열을 생성합니다.
        List<Pos> heights = new ArrayList<Pos>();
        TreeSet<Integer> memoryHeight = new TreeSet<Integer>();
        List<Pos> weights = new ArrayList<Pos>();
        TreeSet<Integer> memoryWeight = new TreeSet<Integer>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine()); // 각 줄을 읽어서 StringTokenizer로 분리합니다.
            pairs[i][0] = Integer.parseInt(st.nextToken()); // 첫 번째 정수를 배열에 저장합니다.
            pairs[i][1] = Integer.parseInt(st.nextToken()); // 두 번째 정수를 배열에 저장합니다.
            memoryHeight.add(pairs[i][1]);
            memoryWeight.add(pairs[i][0]);
        }
        for(int i=1; i<n;i++){
           if(pairs[i-1][0]==pairs[i][0])
               heights.add(new Pos(pairs[i-1][1],pairs[i][1]));
           if(pairs[i-1][1]==pairs[i][1])
               weights.add(new Pos(pairs[i-1][0],pairs[i][0]));
        }
        weights.add(new Pos(pairs[0][0],pairs[n-1][0]));

        int start = memoryHeight.first();
        int end = memoryHeight.last();
        int count = 0;
        for (int i = start; i <= end; i++) {
            int tmp=0;
            for (Pos height : heights) {
                int max = Math.max(height.start,height.end);
                int min = Math.min(height.start,height.end);
                if(min<=i&&i<max)
                    tmp++;
            }
            count = Math.max(count,tmp);
        }
        int h = count;

        start = memoryWeight.first();
        end = memoryWeight.last();
        count = 0;
        for (int i = start; i <= end; i++) {
            int tmp=0;
            for (Pos weight :weights ) {
                int max = Math.max(weight.start,weight.end);
                int min = Math.min(weight.start,weight.end);
                if(min<=i&&i<max)
                    tmp++;
            }
            count = Math.max(count,tmp);
        }
        int w = count;
        System.out.println(h);
        System.out.println(w);

        System.out.println(Math.max(h,w));
        br.close();
        bw.flush();
        bw.close();

    }
}

1. 각 꼭지점을 입력 받으면서, 각각의 x 좌표와 y 좌표를 TreeSet에 저장합니다.
2. 수평선분과 수직선분을 분류하여 각각의 리스트에 추가합니다.
3. 가능한 모든 y 좌표를 순회하면서, 해당 위치에서 수평선이 교차하는 수직선분의 개수를 구합니다.
4. 가능한 모든 x 좌표를 순회하면서, 해당 위치에서 수직선이 교차하는 수평선분의 개수를 구합니다.
5. 교차하는 수직선분의 개수와 교차하는 수펑선분의 개수 중 큰 값을 출력 합니다.

성공한 풀이(스위핑)

시간 복잡도 O(n) 공간 복잡도 O(n)

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

public class Main2 {
    private static final int CAIL = 500000;
    private static final int MAX = 1000010;
    private static int[] CountX = new int[MAX];
    private static int[] CountY = new int[MAX];
    private static List<Pos> vertex = new ArrayList<>();
    public static class Pos{
        int start;
        int end;
        public Pos(int x,int y){
            this.start = x;
            this.end = y;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            // -500000~ 이므로 모든 좌표가 양수가 되도록 500000을 더한다.
            a +=CAIL;
            b +=CAIL;
            // 꼭지점의 대한 모든 정보를 저장한다.
            vertex.add(new Pos(a,b));
        }
        // 꼭짓점 x 좌표값이 다음 번째 x 좌표값과 같다면 y축 선분이 만들어짐
        // 꼭짓점 y 좌표값이 다음 번째 y 좌표값과 같다면 x축 선분이 만들어짐
        for (int i = 0; i < N; i++) {
            int x = vertex.get(i).start;
            int y = vertex.get(i).end;
            int nx = vertex.get((i+1)%N).start;
            int ny = vertex.get((i+1)%N).end;
            // y축 선분 생성, 누적합 기록 첫 선분 시작점 에서 +1, 끝에서 -1
            if(x == nx){
                int StartY = Math.min(y,ny);
                int EndY = Math.max(y,ny);
                CountY[StartY]++;
                CountY[EndY]--;
            } else{
                int StartX = Math.min(x,nx);
                int EndX = Math.max(x,nx);
                CountX[StartX]++;
                CountX[EndX]--;
            }
        }
        // 누적합 계산 작업
        for (int i = 1; i < MAX; i++) {
            CountX[i]+=CountX[i-1];
            CountY[i]+=CountY[i-1];
        }
        int answer = 0;
        // 계산된 누적값의 합계 중 가장 큰 값을 찾기
        for (int i = 1; i < MAX; i++) {
            answer = Math.max(Math.max(CountX[i],CountY[i]),answer);
        }
        System.out.println(answer);
    }
}

1. 각 꼭지점을 입력 받으면서, 좌표값에 일정 값을 더해 모든 좌표가 양수가 되도록 합니다.
2. 각 선분에 대해, 해당 선분이 시작하는 위치에서 카운터를 1 증가시키고, 선분이 끝나는 위치에서 카운터를 1 감소시킵니다. 이를 통해 각 선분이 수평인지 수직인지에 따라 Count_X 배열과 Count_Y 배열에 이벤트를 기록합니다.
3. 각 배열을 순회하면서, 이전 위치에서의 카운터 값을 현재 위치에 더해줍니다. 이를 통해 각 위치에서의 누적 교차 이벤트 개수를 구합니다.
4. 각 위치에서의 누적 교차 이벤트 개수 중 최대값을 찾아 출력합니다.