알고리즘 재활 8일차 - 백준 1629, 1916번

닭꼬치 먹고싶어요 닭꼬치요

 

곱셈

 

 

 

처음에는 수가 커서 해결이 안 되나 했다. 21억 이하 자연수니까~

그래서 나머지 연산에서 수학적으로 접근해서 미리미리 나머지 계산을 처리하고 가야 하는 문제인가..? 라고

접근했었다. 시간을 너무 뺏겼다

 

일단 10의 11승 12의 나머지는? 

계산을 해보자 먼저 10을 Math.pow() 메서드를 이용해 11번 곱할 것이다.

이후 12로 % 연산해줄 테고, 그렇다면 B만큼의 연산을 해야 한다는 소리다.

시간복잡도는 O(N) 이 되겠다.

아이쿠!

하지만 우리에게 주어진 시간은 0.5초.

https://hb-in99.tistory.com/173

알고리즘 시간관련 - 시간 제한, 시간 복잡도

 

아. 지수 연산을 할 때 10의 100승이라면 10의 50승 제곱 이런 식으로 줄여야겠구나.

재귀함수를 통해서 2로 나눠나가면서 한다면 O(Log N)로 줄일 수 있겠구나 로 접근했다.

 

ex) 10의 16승 -> 10의 2승 4 제곱.

연산 횟수 16 -> 4로 Log N

 

바로 작성

 

import java.io.*;
import java.util.*;
 
public class Main { // S1 곱셈
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
 
        System.out.println(recursion(A, B, C));
    }
 
    private static long recursion(long A, long B, long C) {
        // 0 처리 꼭!!!
        if (B == 0) return 1;
        long temp = recursion(A, B / 2, C);
        temp = (temp * temp) % C;
        if (B % 2 != 0) {
            temp = (temp * A) % C;
        }
        return temp;
    }
}

 

---

최소비용 구하기

 

 

다익스트라를 바로 떠올렸다, 간선들이 주어지고 최소 거리를 찾는 것인데

다익스트라의 장점은 해당 위치에 도달하면서 최소 거리를 저장해서 만약 최소거리가 아니라면 갱신하지 않는 알고리즘이다. 그림으로 표현하면 훨씬 쉬울 텐데 나중에 업데이트하겠다 호호

 

https://hb-in99.tistory.com/116

백준 1446번 지름길 S1 - DP, 다익스트라

https://hb-in99.tistory.com/173

알고리즘 시간관련 - 시간 제한, 시간 복잡도

 

 

이전에도 DP 랑 다익스트라를 활용했었었다.

이번엔 더 개선을 위해 우선순위 큐로 기존 N^2 에서 E Log N으로 줄여보자.

 

먼저 우리는 최단 경로를 원하기 때문에 시간 복잡도를 줄이고자 우선순위 큐를 활용해 정렬 했다.

당연히 우리는 비용이 중요하므로 cost로 정렬을 해주었고, 

start 지점에서 해당 위치까지의 최솟값을 저장하므로

기존에 distances에 저장한 값과 내가 현재 이동한 비용의 합을 비교해서 배열을 업데이트해주었다.

기존에 저장된 값보다 작다면 큐에 다시 넣어 해당 경로를 통해 다른 위치도 업데이트 해준다.

 

import java.io.*;
import java.util.*;
 
public class Main { // G5 최소비용 구하기
 
    static ArrayList<ArrayList<Node>> bus;
    public static int N, M, start;
    public static int[] distances;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
 
        bus = new ArrayList<>();
        // 다익스트라 값 배열
        distances = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            distances[i] = Integer.MAX_VALUE;
        }
 
        for (int i = 0; i < N + 1; i++) {
            bus.add(new ArrayList<Node>());
        }
 
        StringTokenizer st;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());
            bus.get(start).add(new Node(end, distance));
        }
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
 
        int answer = logic(start, end);
        System.out.println(answer);
    }
 
    public static int logic(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost));
        pq.add(new Node(start, 0));
        distances[start] = 0;
        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (distances[curNode.idx] < curNode.cost) {
                continue;
            }
 
            for (int i = 0; i < bus.get(curNode.idx).size(); i++) {
                Node nextNode = bus.get(curNode.idx).get(i);
                if (distances[nextNode.idx] > curNode.cost + nextNode.cost) {
                    distances[nextNode.idx] = curNode.cost + nextNode.cost;
                    pq.add(new Node(nextNode.idx, distances[nextNode.idx]));
                }
            }
        }
        return distances[end];
    }
 
    public static class Node {
        int idx, cost;
 
        Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }
}