[백준 5568/2559/1504/11066] 자바

(title: [백준 5568/2559/1504/11066] 자바)

A. 카드놓기 BOJ 5568

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

5568번: 카드 놓기

난이도	Silver 4
풀이 시간	10 분
분류	백트래킹
시간복잡도	O(n^k * k * log n)
공간복잡도

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


public class Main {
    static int n;
    static int k;
    static TreeSet<String> treeSet = new TreeSet<>();
    static boolean [] visited;
    static int [] cards;
    static int [] arr;
    static void dfs(int depth){
        if(depth==k){
            StringBuilder sb = new StringBuilder();
            for(int i = 0 ; i < k ; i++){
                sb.append(String.valueOf(cards[arr[i]]));
            }
            treeSet.add(sb.toString());
            return;
        } else{
            for(int i = 0 ; i < n ; i++){
                if(!visited[i]){
                    visited[i] = true;
                    arr[depth] = i;
                    dfs(depth+1);
                    visited[i] = false;
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        n = Integer.parseInt(br.readLine());
        // n 장의 수 중에서
        k = Integer.parseInt(br.readLine());
        // k 장을 선택하여 수를 만든다.
        visited = new boolean[n];
        cards = new int[n];
        arr = new int[n];

        for(int i = 0 ; i < n ; i++){
            cards[i] = Integer.parseInt(br.readLine());
        }
        dfs(0);

        bw.write(treeSet.size()+"\n");
        bw.flush();
        bw.close();
    }
}

 

 

 

 

B. 수열 BOJ 2559

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

2559번: 수열

난이도	Silver 3
풀이 시간	15 분
분류	누적합 + 슬라이딩 윈도우
시간복잡도	O(N)
공간복잡도

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int k = Integer.parseInt(stk.nextToken());

        int [] base = new int[n+1];
        int [] prefix = new int[n+1];
        stk = new StringTokenizer(br.readLine());
        for(int i = 1 ; i <= n; i++){
            base[i] = Integer.parseInt(stk.nextToken());
        }
        prefix[0] = base[1];
        for(int i = 1 ; i<=n; i++){
            prefix[i] = prefix[i-1] + base[i];
        }

        int st = 1;
        int end = k;
        int max = -Integer.MAX_VALUE;
        while(end <= n){
            int sum = prefix[end] - prefix[st-1];
            max = Math.max(sum, max);
            st++;
            end++;
        }
        bw.write(max+"\n");
        bw.flush();
        bw.close();
    }
}

 

 

 

C. 특정한 최단 경로 BOJ 1504

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

1504번: 특정한 최단 경로

난이도	Gold 4
풀이 시간	1시간
분류	다익스트라
시간복잡도	O(EogV)
공간복잡도

입력을 잘못 받아놓고, 40분동안 맞왜틀했다 😢

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

public class Main {
    static ArrayList<node>[] graph;
    static int n;
    static int e;
    static int inf = 200000*1000+1;

    static class node implements Comparable<node> {
        int to;
        int w;

        public node(int to, int w) {
            this.to = to;
            this.w = w;
        }

        @Override
        public int compareTo(node o) {
            if (this.w > o.w) return -1;
            else return 1;
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;
        stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        e = Integer.parseInt(stk.nextToken());
        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < e; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            int c = Integer.parseInt(stk.nextToken());
            graph[a].add(new node(b, c));
            graph[b].add(new node(a, c));
        }
        stk = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(stk.nextToken());
        int v2 = Integer.parseInt(stk.nextToken());

        int [] dist1 = new int[n+1];
        int [] dist2 = new int[n+1];
        int [] dist3 = new int[n+1];

        dijkstra(1, n, dist1);
        dijkstra(v1, v2, dist2);
        dijkstra(v2, n, dist3);

        long case1 = dist1[v1] + dist2[v2] + dist3[n];
        // case 2 : 1->v2->v1->n
        long case2 = dist1[v2] + dist3[v1] + dist2[n];
        long ans = Math.min(inf, case1);
        if(dist2[v2]==inf || ans==inf || dist3[n] == inf){
            //v1-n, v2-n 으로 연결된 경로가 없다면
            System.out.println("-1\n");
            return;
        }
        ans = Math.min(ans, case2);
        bw.write(ans+"\n");
        bw.flush();
        bw.close();
    }
    static void dijkstra(int start, int end, int [] dist){
        Arrays.fill(dist, inf);
        dist[start] = 0;

        PriorityQueue<node> pq = new PriorityQueue<>();
        pq.add(new node(start, 0));
        while(!pq.isEmpty()){
            node now = pq.poll();
            for(node cur : graph[now.to]){
                if(dist[cur.to] >= dist[now.to] + cur.w){
                    dist[cur.to] = dist[now.to] + cur.w;
                    pq.add(new node(cur.to, dist[cur.to]));
                }
            }
        }
    }
}

 

 

D. 파일 합치기 BOJ 11066

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

11066번: 파일 합치기

난이도	Gold3
풀이 시간	1시간 정도 고민하다가 점화식이 너무 안떠올라서, 구글링의 도움으로 코드를 작성했다 😢
분류	DP
시간복잡도	O(N^3)
공간복잡도

[Bottom-up]

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

public class Main {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;
        int tc = Integer.parseInt(br.readLine());
        while (tc > 0) {
            tc--;
            int k = Integer.parseInt(br.readLine());
            int[] arr = new int[k + 1];
            stk = new StringTokenizer(br.readLine());
            for (int i = 1; i <= k; i++) {
                arr[i] = Integer.parseInt(stk.nextToken());
            }

            long ans = solve(arr, k);
            bw.write(ans + "\n");
        }

        bw.flush();
        bw.close();
    }

    private static int solve(int[] arr, int k) {
        int[][] dp = new int[k + 1][k + 1];
        int[] prefix = new int[k + 1];


        for (int i = 1; i <= k; i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        } // 누적합

        // 파일 개수가 세 개 이상이라면 ( mid ; 중간 지점 )
        // dp[i][j] = min( dp[i][j] , dp[i][mid] + dp[mid+1][j] + sum(i~j) )
        for (int div = 1; div < k; div++) {
            for (int i = 1; i+div <= k; i++) {
                int j = i + div;
                dp[i][j] = Integer.MAX_VALUE;
                for (int mid = i; mid < j; mid++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][mid] + dp[mid + 1][j] + getSum(i, j, prefix));
                }
            }
        }


        return dp[1][k];
    }

    private static int getSum(int st, int end, int[] prefix) {
        return prefix[end] - prefix[st - 1];
    }
}

[Top-down]

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

public class Main {
    static int[][] dp;
    static int[] arr;
    static int[] prefix;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;
        int tc = Integer.parseInt(br.readLine());
        while (tc > 0) {
            tc--;
            int k = Integer.parseInt(br.readLine());
            arr = new int[k + 1];
            stk = new StringTokenizer(br.readLine());
            for (int i = 1; i <= k; i++) {
                arr[i] = Integer.parseInt(stk.nextToken());
            }

            dp = new int[k + 1][k + 1];
            prefix = new int[k + 1];

            for (int i = 1; i <= k; i++) {
                prefix[i] = prefix[i - 1] + arr[i];
            } // 누적합

            for(int i = 0 ; i <=k; i++){
                for(int j = 0 ; j <=k; j++){
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }

            long ans = solve_topdown(1, k);
            bw.write(ans + "\n");
        }

        bw.flush();
        bw.close();
    }

    private static int solve_topdown(int left, int right) {
        if (dp[left][right] != Integer.MAX_VALUE) {
            return dp[left][right];
        }
        if (left == right) {
            return dp[left][right] = 0;
        }
        if (left + 1 == right) {
            return dp[left][right] = arr[left] + arr[right];
        }
        for (int mid = left; mid < right; ++mid) {
            int nleft = solve_topdown(left, mid);
            int nright = solve_topdown(mid + 1, right);
            dp[left][right] = Math.min(dp[left][right], nleft + nright);
        }
        return dp[left][right] += getSum(left, right, prefix);
    }

    private static int getSum(int st, int end, int[] prefix) {
        return prefix[end] - prefix[st - 1];
    }
}