알고리즘 문제풀이 3-2

문제 1 / 제로 카드 게임

-목표 : 카드 더미에서 뽑은 N개의 카드에 적힌 수를 모은 카드 배열 정수 cards를 이용해서 만들 수 있는 가장 작은 패널티를 구하는 프로그램 구현

 

문제 풀이

dp를 이용하여 부분합을 찾고, target과 가장 가까운 bestSum을 선택하여 풀이하였다.

 

최종 코드

import java.util.*;
class Solution {
    public int solution(int N, int[] cards) {
        int answer = 0;
        int totalSum = Arrays.stream(cards).sum();
        int target = totalSum / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for(int card : cards){
            for(int j = target; j>= card; j--){
                if(dp[j - card]){
                    dp[j] = true;
                }
            }
        }

        int bestSum =0;
        for(int i=target; i>=0; i--){
            if(dp[i]){
                bestSum = i;
                break;
            }
        }

        return Math.abs(totalSum - 2 * bestSum);
    }
}

---

문제 2 / 세금

-목표 : 주어진 세금 납부 금액에서 특정 범위 내의 사람의 수를 구하는 프로그램 구현

 

문제 풀이

이진 탐색을 사용하여 사람의 수를 구하였다.

X 이상 값이 처음 등장하는 위치 / Y 이하 값이 마지막으로 등장하는 위치 찾기

 

최종 코드

import java.util.*;
class Solution {
    public int[] solution(int N, int K, int[] arr, int[][] queries) {
        int[] answer = new int[K];
        Arrays.sort(arr);

        for(int i=0; i<K; i++){
            int X = queries[i][0];
            int Y = queries[i][1];

            int left = lowerBound(arr, X);
            int right = upperBound(arr, Y);
            answer[i] = right - left;
        }
        return answer;
    }
    private int lowerBound(int[] arr, int X){
        int left =0, right = arr.length;
        while(left<right){
            int mid = (left + right) /2;
            if(arr[mid] < X) left = mid + 1;
            else right = mid;
        }
        return left;
    }
    private int upperBound(int[] arr, int Y){
        int left = 0, right = arr.length;
        while(left < right){
            int mid = (left + right) / 2;
            if(arr[mid] <= Y)left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

---

문제 3 / 봉술가

-목표 : 봉술가의 시작 위치를 결정하기 위해 거리가 최대가 되는 빈 칸을 계산하는 프로그램 구

 

문제 풀이

풀지 못함

 

최종 코드

---