알고리즘(배달, 스티커 모으기2)

[배달]

* 알고리즘

• 다익스트라

 

* 로직

• 인접리스트를 생성한다(양방향)
• 1번 마을부터 시작하기 때문에 시작노드를 1로 설정한다
• 다익스트라를 진행한다
• 진행한 후 distance[] 값이 K 이하라면 답을 카운팅한다

 

//배달
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

class NodeInfo_Delivery implements Comparable<NodeInfo_Delivery>{
    public int nodeIdx;
    public int distance;

    public NodeInfo_Delivery(int nodeIdx, int distance) {
        this.nodeIdx = nodeIdx;
        this.distance = distance;
    }

    @Override
    public int compareTo(NodeInfo_Delivery o) {
        return this.distance - o.distance;
    }
}

public class Problem_Delivery {

    static ArrayList<ArrayList<NodeInfo_Delivery>> adjList;
    static int[] distance;
    static boolean[] checked;

    public static void main(String[] args) {
        int N = 5;
        int[][] road = {
                {1,2,1},{2,3,3},{5,2,2},{1,4,2},{5,3,1},{5,4,2}
        };
        int K = 3;
        int answer = solution(N, road, K);
        System.out.println(answer);
    }

    public static int solution(int N, int[][] road, int K) {
        int answer = 0;
        adjList = new ArrayList<>();
        distance = new int[N+1];
        checked = new boolean[N+1];

        for(int i=0; i<=N; ++i){
            adjList.add(new ArrayList<>());
        }

        //인접 리스트 생성
        for(int[] input : road){
            int v1 = input[0];
            int v2 = input[1];
            int cost = input[2];

            adjList.get(v1).add(new NodeInfo_Delivery(v2, cost));
            adjList.get(v2).add(new NodeInfo_Delivery(v1, cost));
        }

        //다익스트라 진행
        int startNode = 1;
        doProcess(startNode);

        for(int i=1; i<=N; ++i){
            if(distance[i] <= K) answer++;
        }

        return answer;
    }

    private static void doProcess(int startNode) {
        Arrays.fill(distance, Integer.MAX_VALUE);
        PriorityQueue<NodeInfo_Delivery> priorityQueue = new PriorityQueue<>();

        distance[startNode] = 0;
        priorityQueue.offer(new NodeInfo_Delivery(startNode, distance[startNode]));

        while (!priorityQueue.isEmpty()){
            NodeInfo_Delivery q = priorityQueue.poll();
            if(checked[q.nodeIdx]) continue;

            checked[q.nodeIdx] = true;
            for(NodeInfo_Delivery adjNode : adjList.get(q.nodeIdx)){
                if(distance[adjNode.nodeIdx] > distance[q.nodeIdx] + adjNode.distance){
                    distance[adjNode.nodeIdx] = distance[q.nodeIdx] + adjNode.distance;
                    priorityQueue.offer(new NodeInfo_Delivery(adjNode.nodeIdx, distance[adjNode.nodeIdx]));
                }
            }
        }
    }

}

 

 

[스티커 모으기2]

* 알고리즘

• 동적 계획법(DP)

 

* 로직

• 첫 번째 스티커부터 떼는 경우와 두 번째 스티커부터 떼는 경우로 나눌 수 있다
• 첫 번째 스티커부터 떼는 경우
  • dp_first[0] = dp_first[1] = sticker[0] 이다 (두 번째 칸은 인접하기때문에 같은 값으로 넣어줌)
  • 이후 dp_first[i] = Math.max(dp_first[i-2] + sticker[i], dp_first[i-1])을 통해 갱신해준다
    즉, dp_first[i]라는 말은 현재 위치에서 얻을 수 있는 최댓값이다 => 모든 경우를 dp로 고려해줄 수 있다
• 두 번째 스티커부터 떼는 경우
  • dp_second[0] = 0, dp_second[1] = sticker[1] 이다
  • 이후 dp_second[i] = Math.max(dp_second[i-2] + sticker[i], dp_second[i-1])을 통해 갱신해준다
    즉, dp_second[i]라는 말은 현재 위치에서 얻을 수 있는 최댓값이다 => 모든 경우를 dp로 고려해줄 수 있다
• 위 2가지 경우의 값 중 최댓값을 출력한다

 

//스티커 모으기2

public class Problem_Sticker2 {

    public static void main(String[] args) {
        int[] sticker = {14, 6, 5, 11, 3, 9, 2, 10};
        int answer = solution(sticker);
        System.out.println(answer);
    }

    public static int solution(int sticker[]) {
        int answer = 0;
        int size = sticker.length;
        if(size == 1) return sticker[0];
        else if(size == 2) return Math.max(sticker[0], sticker[1]);

        int[] dp_first = new int[size-1];
        int[] dp_second = new int[size];

        dp_first[0] = sticker[0];
        dp_first[1] = sticker[0];
        for(int i=2; i<dp_first.length; ++i){
            dp_first[i] = Math.max(dp_first[i-2] + sticker[i], dp_first[i-1]);
        }

        dp_second[0] = 0;
        dp_second[1] = sticker[1];
        for(int i=2; i<dp_second.length; ++i){
            dp_second[i] = Math.max(dp_second[i-2] + sticker[i], dp_second[i-1]);
        }

        answer = Math.max(dp_first[dp_first.length-1], dp_second[dp_second.length-1]);
        return answer;
    }
}

 

스티커 모으기2 문제의 경우 이전에 풀어봤던 도둑질 문제와 유사하기 때문에 관련 링크로 첨부한다

 

https://uyoo-story.tistory.com/50

알고리즘(도둑질)