[백준 2798/2231/14889/2606] 자바

A. 블랙잭 BOJ 2798

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

2798번: 블랙잭

난이도	Bronze 2
풀이 시간	10 분
분류	브루트포스
시간복잡도
공간복잡도	O(100+100)

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


public class Main {
    static int ans = -1;
    static int m;
    static int n;
    static int [] arr;
    static int [] nums = new int[3];
    static boolean [] visited;
    private static void dfs(int k){
        if(k==3){
            int sum = 0;
            for(int i = 0 ; i < 3; i++){
                sum += nums[i];
            }
            if(sum > m) {
                return;
            } else { // sum <=m
                ans = Math.max(ans, sum);
                return;
            }
        } else {
            for(int i = 0 ; i < n ; i ++){
                if(!visited[i]){
                    visited[i] = true;
                    nums[k] = arr[i];
                    dfs(k+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;

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

        arr = new int[n];
        visited = new boolean[n];
        stk = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n ; i ++){
            arr[i] = Integer.parseInt(stk.nextToken());
        }
        dfs(0);
        
        bw.write(ans+"\n");
        bw.flush();
        bw.close();
    }
}

 

 

 

B. 분해합 BOJ 2231

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

2231번: 분해합

난이도	Bronze 2
풀이 시간	5 분
분류	브루트포스
시간복잡도	O(N)
공간복잡도	O(1)

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


public class Main {
    static int ans = -1;
    static int m;
    static int n;
    static int [] arr;
    static int [] nums = new int[3];
    static boolean [] visited;
    private static void dfs(int k){
        if(k==3){
            int sum = 0;
            for(int i = 0 ; i < 3; i++){
                sum += nums[i];
            }
            if(sum > m) {
                return;
            } else { // sum <=m
                ans = Math.max(ans, sum);
                return;
            }
        } else {
            for(int i = 0 ; i < n ; i ++){
                if(!visited[i]){
                    visited[i] = true;
                    nums[k] = arr[i];
                    dfs(k+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;

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

        int ans = n+1;
        for(int i = 1 ; i<=n-1; i++){
            int target = i;
            int save = target;
            int pSum=target;
            while(target>0){
                pSum += target%10;
                target = target/10;
            }
            if(pSum == n){
                ans = Math.min(ans, save);
            }
        }

        if(ans==n+1){
            bw.write(0+"\n");
        } else {
            bw.write(ans+"\n");
        }
        bw.flush();
        bw.close();
    }
}

 

 

 

C. 스타트와 링크 BOJ 14889

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

14889번: 스타트와 링크

난이도	Silver 2
풀이 시간	30 분
분류	백트래킹
시간복잡도	O(nC_n/2 + n^2)
공간복잡도	O(20*20+20*2)

 

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


public class Main {
    static int n;
    static long ans = Integer.MAX_VALUE;
    static int[][] power;
    static int[] entry;
    static boolean[] visited;

    private static void getScore() {
        long ret = 0;

        long A = 0;
        long B = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i; j < n; j++) {
                if (visited[i] == true && visited[j] == true) {
                    A+=(power[i][j]+power[j][i]);
                } else if (visited[i] == false && visited[j] == false) {
                    B+=(power[i][j]+power[j][i]);
                }
            }
        }

        ans = Math.min(ans, Math.abs(A-B));
    }

    private static void dfs(int k, int idx) {
        if (k == n/2) {
            // 점수 계산
            getScore();
            return;
        } else {
            for (int i = idx; i < n; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    dfs(k + 1, i + 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());
        power = new int[n][n];
        visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                power[i][j] = Integer.parseInt(stk.nextToken());
            }
        }
        dfs(0, 0);

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

 

D. 바이러스 BOJ 2606

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

2606번: 바이러스

난이도	Silver 3
풀이 시간	5 분
분류	그래프 탐색
시간복잡도	O(V+E)
공간복잡도	O(V+E)

 

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class Main {
    static ArrayList<Integer>[] graph;
    static boolean [] visited;
    private static void dfs(int v){
        if(!visited[v])
            visited[v] = true;
        for(int cur : graph[v]){
            // 연결 노드 탐색
            if(!visited[cur]){
                visited[cur] = true;
                dfs(cur);
            }
        }
    }
    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 n = Integer.parseInt(br.readLine()); // 노드의 수
        int m = Integer.parseInt(br.readLine()); // 엣지의 수

        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++)
            graph[i] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }

        visited = new boolean[n+1];
        dfs(1);

        int cnt = 0;
        for(int i = 2 ; i<=n; i++){
            if(visited[i]){
                cnt++;
            }
        }
        bw.write(cnt+"\n");
        bw.flush();
        bw.close();
    }
}