딩코딩 : Computer Science 블로그

https://leetcode.com/problems/split-array-largest-sum/submissions/

class Solution {
public:
    bool decide(vector<int>& nums, int k, int m){
        int cnt = 0;
        
        int add = 0;
        for(int i=0; i<nums.size(); i++){
            add += nums[i];
            
            if(add==k){
                add = 0;
                cnt++;
            }
            else if(add>k){
                add = nums[i];
                cnt++;
            }
        }
        
        if(add>0) cnt++;
        
        
        return cnt<=m;
    }
    
    
    
    int splitArray(vector<int>& nums, int m) {
        int lo = 0;
        int hi = 0;
        int maxx = 0;
        for(int i=0; i<nums.size();i++){
            hi += nums[i];
            maxx = max(maxx, nums[i]);
        }
        
        
        while(lo<=hi){
            int mid = (lo+hi)/2;
            
            if(mid>=maxx && decide(nums, mid, m)){
                hi = mid-1;
            }
            else{
                lo = mid+1;
            }
        }
        
        return lo;
    }
};

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

import java.util.*;

class Edge implements Comparable<Edge>{
    int x, c;
    Edge(int x, int c){
        this.x = x;
        this.c = c;
    }

    public int compareTo(Edge e){
        return c - e.c;
    }
}

public class Main {

    static int v, e, p;
    static ArrayList<Edge> adj[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        v = sc.nextInt();
        e = sc.nextInt();
        p = sc.nextInt();

        adj = new ArrayList[v+1];
        for(int i=0; i<=v; i++){
            adj[i] = new ArrayList<>();
        }


        for(int i=0; i<e; i++){
            int a,b,c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();

            adj[a].add(new Edge(b,c));
            adj[b].add(new Edge(a,c));
        }

        if(dikstra(1,v)==dikstra(1,p) + dikstra(p,v)){
            System.out.println("SAVE HIM");
        }
        else System.out.println("GOOD BYE");

    }

    static int dikstra(int st, int en){
        if(st==en) return 0;

        PriorityQueue<Edge> Q = new PriorityQueue<>();
        int dist[] = new int[v+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        Q.add(new Edge(st,0));

        while(!Q.isEmpty()){
            Edge cur = Q.poll();

            for(Edge nx : adj[cur.x]){
                if(dist[nx.x] > cur.c + nx.c){
                    dist[nx.x] = cur.c + nx.c;
                    Q.add(new Edge(nx.x, cur.c+nx.c));
                }
            }
        }

        return dist[en];
    }
}

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

일반적으로 최소비용만 고려하는 다익스트라와 달리

이 문제는 고려해야하는 변수가 최소시간과 함께 M 이하의 cost를 고려해야한다.

즉 변수가 두개이기 때문에

메모리를 더 사용하여 cost에 따른 최소시간을 저장해둘 필요가 있다.

그렇기에 dp가 필요하다.

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


class Edge implements Comparable<Edge>{
    int x,c,d;
    Edge(int x, int c, int d){
        this.x = x;
        this.c = c;
        this.d = d;
    }

    public int compareTo(Edge e){
        return d - e.d;
    }
}


public class Main {
    static ArrayList<Edge> adj[];
    static PriorityQueue<Edge> Q = new PriorityQueue<>();
    static int dp[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        String[] split;
        for (int T = 0; T < t; T++) {
            int n, m, k;
            split = br.readLine().split(" ");
            n = Integer.parseInt(split[0]);
            m = Integer.parseInt(split[1]);
            k = Integer.parseInt(split[2]);

            dp = new int[n+1][m+1];
            Q.clear();
            adj = new ArrayList[n+1];
            for(int i=1; i<=n; i++){
                adj[i] = new ArrayList<Edge>();
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }


            for(int i=0; i<k; i++){
                int a,b,c,d;
                split = br.readLine().split(" ");
                a = Integer.parseInt(split[0]);
                b = Integer.parseInt(split[1]);
                c = Integer.parseInt(split[2]);
                d = Integer.parseInt(split[3]);

                adj[a].add(new Edge(b,c,d));
            }

            Q.add(new Edge(1,0,0));


            int ans = Integer.MAX_VALUE;



            while(!Q.isEmpty()){
                Edge cur = Q.poll();

                if(cur.x == n) {
                    ans = cur.d;
                    break;
                }

                for(Edge nx : adj[cur.x]){
                    if(cur.c + nx.c > m) continue;
                    if(dp[nx.x][cur.c+nx.c] <= cur.d + nx.d) continue;
                    dp[nx.x][cur.c+nx.c] = cur.d + nx.d;
                    Q.add(new Edge(nx.x, cur.c + nx.c , cur.d + nx.d));
                }
            }
            

            if(ans!=Integer.MAX_VALUE){
                bw.write(Integer.toString(ans));
            }
            else bw.write("Poor KCM");
            bw.write("\n");

        }
        bw.flush();
    }
}

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

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


class Node implements Comparable<Node>{
    int x, y, c;

    Node(int x, int y, int c){
        this.x = x;
        this.y = y;
        this.c = c;
    }

    @Override
    public int compareTo(Node n){
        return c - n.c;
    }

}



class Edge implements Comparable<Edge>{
    int x,c;
    Edge(int x, int c){
        this.x = x;
        this.c = c;
    }

    @Override
    public int compareTo(Edge e){
        return c - e.c;
    }
}


public class Main {
    static int n, k;
    static int unf[];
    static long dist[];
    static PriorityQueue<Node> Q = new PriorityQueue<Node>();
    static PriorityQueue<Edge> q = new PriorityQueue<Edge>();
    static ArrayList<Edge> adj[];

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");

        int n = Integer.parseInt(split[0]);
        int k = Integer.parseInt(split[1]);



        adj = new ArrayList[n];
        unf = new int[n];
        dist = new long[n];

        for(int i=0; i<n; i++){
            adj[i] = new ArrayList<Edge>();
        }

        Arrays.fill(unf,-1);
        Arrays.fill(dist, Long.MAX_VALUE);

        for(int i=0; i<k; i++){
            int a, b, c;
            split = br.readLine().split(" ");
            a = Integer.parseInt(split[0]);
            b = Integer.parseInt(split[1]);
            c = Integer.parseInt(split[2]);

            Q.add(new Node(a,b,c));
        }

        long ans = 0;

        while(!Q.isEmpty()){
            Node cur = Q.poll();
            int x = cur.x;
            int y = cur.y;
            int c = cur.c;


            if(Find(x)!=Find(y)) {
                Union(x, y);
                ans += c;
                adj[x].add(new Edge(y,c));
                adj[y].add(new Edge(x,c));
            }
        }


        q.add(new Edge(0,0));

        int stNode = -1;

        while(!q.isEmpty()){
            Edge cur = q.poll();
            int x = cur.x;
            int c = cur.c;

            if(dist[x] < c ) continue;
            dist[x] = c;
            stNode = x;

            for(int i=0; i<adj[x].size(); i++){
                Edge nx = adj[x].get(i);

                if(dist[nx.x] > c + nx.c){
                    q.add(new Edge(nx.x, c+nx.c));
                }
            }
        }

        Arrays.fill(dist, Long.MAX_VALUE);

        q.add(new Edge(stNode, 0));


        long ansdist = 0;
        while(!q.isEmpty()){
            Edge cur = q.poll();
            int x = cur.x;
            int c = cur.c;

            if(dist[x] < c ) continue;
            dist[x] = c;
            ansdist = c;

            for(int i=0; i<adj[x].size(); i++){
                Edge nx = adj[x].get(i);

                if(dist[nx.x] > c + nx.c){
                    q.add(new Edge(nx.x, c+nx.c));
                }
            }
        }





        System.out.println(ans);
        System.out.println(ansdist);


    }



    static int Find(int x){
        if(unf[x]==-1) return x;
        return Find(unf[x]);
    }

    static void Union(int a, int b){
        int a1 = Find(a);
        int b1 = Find(b);

        if(a1!=b1){
            unf[a1] = b1;
        }
    }

}

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

1. 플로이드 와샬에서 3중 for문을 작성할 때 i, j, k 의 순서가 중요하다

2. 플로이드 와샬에서 k노드를 통해 경로를 업데이트 할 때마다 k노드는 도착점 이전의 가장 마지막 노드가 된다.

따라서 출발점 이후 첫번째 노드를 구하려면

현재 문제에서 그래프가 양방향 그래프이기 때문에 출발점 도착점 기준 가장 마지막 노드가

도착점 출발점의 첫번째 노드가 된다.

이를 이용하면 추가적인 재귀나 반복 없이 첫번째 노드를 구할 수 있다.

import java.util.*;


class Edge implements Comparable<Edge>{
    int x, c;

    Edge(int x, int c){
        this.x = x;
        this.c = c;
    }

    @Override
    public int compareTo(Edge e){
        return c- e.c;
    }
}


public class Main {
    static int[][] ans, dist,  adj;
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        ans = new int[n+1][n+1];
        dist = new int[n+1][n+1];
        adj = new int[n+1][n+1];

        for(int i=1; i<=n; i++){
            Arrays.fill(dist[i], Integer.MAX_VALUE/2);
            Arrays.fill(adj[i],Integer.MAX_VALUE/2);
            adj[i][i] = 0;
            dist[i][i] = 0;
        }

        for(int i=0; i<m; i++){
            int a= sc.nextInt();
            int b =sc.nextInt();
            int c = sc.nextInt();

            dist[a][b] = Math.min(dist[a][b],c);
            dist[b][a] = Math.min(dist[b][a],c);


            ans[a][b] = a;
            ans[b][a] = b;
        }


        for(int k=1; k<=n;k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(dist[i][j] > dist[i][k] + dist[k][j]){
                        dist[i][j] = dist[i][k] + dist[k][j];
                        ans[i][j] = ans[k][j];
                    }
                }
            }
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j) System.out.print("- ");
                else System.out.print(ans[j][i] + " ");
            }
            System.out.println();
        }
    }
}

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

import java.util.*;


class Edge implements Comparable<Edge>{
    int x, c;

    Edge(int x, int c){
        this.x = x;
        this.c = c;
    }

    @Override
    public int compareTo(Edge e){
        return c - e.c;
    }

}

public class Main {
    static int n,m;
    static ArrayList<Edge> adj[];
    static int dist[];
    static PriorityQueue<Edge> Q = new PriorityQueue<>();


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        adj = new ArrayList[n+1];
        dist = new int[n+1];

        Arrays.fill(dist,Integer.MAX_VALUE);

        for(int i=0; i<=n; i++){
            adj[i] = new ArrayList<Edge>();
        }

        for(int i=0; i<m; i++){
            int a, b, c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();

            adj[a].add(new Edge(b,c));
            adj[b].add(new Edge(a,c));
        }


        dist[1] = 0;
        Q.add(new Edge(1,0));


        while(!Q.isEmpty()){
            Edge cur = Q.poll();

            if(cur.c > dist[cur.x]) continue;

            dist[cur.x] = cur.c;

            for(int i=0; i<adj[cur.x].size();i++){
                Edge nx = adj[cur.x].get(i);

                if(dist[nx.x] > nx.c + cur.c){
                    Q.add(new Edge(nx.x, nx.c + cur.c));
                }
            }
        }


        System.out.println(dist[n]);
    }
}

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

import java.util.*;

class Edge implements Comparable<Edge>{
    int x, y, cost;

    Edge(int x, int y, int cost){
        this.x = x;
        this.y = y;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge e){
        return cost - e.cost;
    }
}

public class Main {

    static int unf[];

    static int Find(int x){
        if(unf[x]==-1) return x;
        return unf[x] = Find(unf[x]);
    }

    static void Union(int a, int b){
        int a1 = Find(a);
        int b1 = Find(b);

        if(a1!=b1){
            unf[a1] = b1;
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        ArrayList<Edge> list = new ArrayList<>();

        Collections.sort(list);

        int n = sc.nextInt();
        unf = new int[n+1];

        Arrays.fill(unf,-1);


        for(int i=1; i<=n; i++){
            int p = sc.nextInt();
            list.add(new Edge(0,i,p));
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                int p = sc.nextInt();
                if(i==j) continue;
                list.add(new Edge(i,j,p));
            }
        }

        Collections.sort(list);

        int ans = 0;
        for(int i=0; i<list.size(); i++){
            Edge cur = list.get(i);
            int x = cur.x;
            int y = cur.y;
            int c = cur.cost;

            if(Find(x)!=Find(y)){
                Union(x,y);
                ans += c;
            }
        }

        System.out.println(ans);

    }
}

import java.util.*;

class Edge implements Comparable<Edge>{
    int x, y, cost;

    Edge(int x, int y, int cost){
        this.x = x;
        this.y = y;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge e){
        return cost - e.cost;
    }
}

public class Main {

    static int unf[];

    static int Find(int x){
        if(unf[x]==-1) return x;
        return unf[x] = Find(unf[x]);
    }

    static void Union(int a, int b){
        int a1 = Find(a);
        int b1 = Find(b);

        if(a1!=b1){
            unf[a1] = b1;
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        PriorityQueue<Edge> list = new PriorityQueue<>();

        int n = sc.nextInt();
        unf = new int[n+1];

        Arrays.fill(unf,-1);


        for(int i=1; i<=n; i++){
            int p = sc.nextInt();
            list.add(new Edge(0,i,p));
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                int p = sc.nextInt();
                if(i==j) continue;
                list.add(new Edge(i,j,p));
            }
        }


        int ans = 0;
        while(!list.isEmpty()){
            Edge cur = list.poll();
            int x = cur.x;
            int y = cur.y;
            int c = cur.cost;

            if(Find(x)!=Find(y)){
                Union(x,y);
                ans += c;
            }
        }

        System.out.println(ans);

    }
}

compareTo의 return값이 음수면 객체 본인이 작은 것이고

양수면 객체 본인이 큰 것이다.

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

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

class Edge implements Comparable<Edge>{
//    boolean canUse;
    int x, y;
    Edge(int x, int y){
//        canUse = true;
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }

    @Override
    public int compareTo(Edge edge){
        if(x!=edge.x) return (edge.x - x);
        else return (edge.y - y);
    }
}

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        for(int T=0; T<t; T++){
            int n = Integer.parseInt(br.readLine());

            ArrayList<Edge> list = new ArrayList<>();

            for(int i=0; i<n; i++){
                String[] split = br.readLine().split(" ");

                int a= Integer.parseInt(split[0]);
                int b= Integer.parseInt(split[1]);

                list.add(new Edge(a,b));

            }
            Collections.sort(list, Collections.reverseOrder());

            int comp = 10000000;
            int ans = 0;
            for(int i=0; i<n; i++){
                if(comp > list.get(i).y){
                    ans++;
                    comp = list.get(i).y;
                }
            }

            bw.write(Integer.toString(ans));

            bw.write("\n");
        }
        bw.flush();
    }
}