[백준 2580/14888/13305/10844] JAVA

A. 연산자 끼워넣기 BOJ 14888

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

난이도	Silver 1
풀이 시간	40 분
분류	백트래킹
시간복잡도	O(4^n)
공간복잡도	O(N+M)

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

public class Main {
    static int n;
    static int [] nums;
    static int [] oper = new int [4];
    static StringBuilder sb = new StringBuilder();
    static int min=Integer.MAX_VALUE;
    static int max= Integer.MIN_VALUE;
    static void dfs(int num, int idx){
        if(idx==n){
            min = Math.min(num, min);
            max = Math.max(num, max);
            return;
        } else {
            for(int i = 0 ; i < 4 ; i++){
                if(oper[i]>0){
                    oper[i]--;
                    switch(i){
                        case 0:
                            dfs(num+nums[idx], idx+1);
                            break;
                        case 1:
                            dfs(num-nums[idx], idx+1);
                            break;
                        case 2:
                            dfs(num*nums[idx], idx+1);
                            break;
                        case 3:
                            dfs(num/nums[idx], idx+1);
                            break;
                    }
                    oper[i]++;
                }
            }
        }
    }

    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());
        nums = new int [n];
        stk = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n; i ++){
            nums[i] = Integer.parseInt(stk.nextToken());
        }
        stk = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < 4 ; i++){
            oper[i] = Integer.parseInt(stk.nextToken());
        }

        dfs(nums[0], 1);

        bw.write(max+"\n");
        bw.write(min+"\n");

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

 

 

 

 

B. 스도쿠 BOJ 2580

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

2580번: 스도쿠

난이도	Gold 4
풀이 시간	50 분
분류	백트래킹, 구현
시간복잡도	O(N!)
공간복잡도	O(9*9+9*10*3)

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

public class Main {
    static int[][] sudoku = new int[9][9];
    static boolean[][] rowCheck = new boolean[9][10];
    static boolean[][] colCheck = new boolean[9][10];
    static boolean[][] boxCheck = new boolean[9][10];
    static boolean isitdone;

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static void dfs(int k) throws IOException {
        if(isitdone) return;
        int x_pos = k % 9;
        int y_pos = k / 9;
        if (k == 81) {
            isitdone=true;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(sudoku[i][j]+" ");
                }
                System.out.println();
            }
            return;
        }
        if (sudoku[y_pos][x_pos] == 0) {
            for (int t = 1; t <= 9; t++) {
                if(rowCheck[y_pos][t]==false && colCheck[x_pos][t]==false && boxCheck[(y_pos / 3) * 3 + x_pos / 3][t]==false){
                    rowCheck[y_pos][t] = true;
                    colCheck[x_pos][t] = true;
                    boxCheck[(y_pos / 3) * 3 + x_pos / 3][t] = true;
                    sudoku[y_pos][x_pos] = t;
                    dfs(k + 1);
                    sudoku[y_pos][x_pos] = 0;
                    rowCheck[y_pos][t] = false;
                    colCheck[x_pos][t] = false;
                    boxCheck[(y_pos / 3) * 3 + x_pos / 3][t] = false;
                }
            }
        } else dfs(k+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;

        for (int i = 0; i < 9; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = Integer.parseInt(stk.nextToken());
                rowCheck[i][sudoku[i][j]] = true;
                colCheck[j][sudoku[i][j]] = true;
                boxCheck[(i / 3) * 3 + j / 3][sudoku[i][j]] = true;
            }
        }

        dfs(0);


    }
}

 

 

 

C. 주유소 BOJ 13305

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

13305번: 주유소

난이도	Silver 3
풀이 시간	15 분
분류	그리디
시간복잡도	O(N)
공간복잡도	O(N)

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

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 n = Integer.parseInt(br.readLine()); // 도시의 개수
        long[] dosi = new long[n];
        long[] dist = new long[n];
        long total_cost = 0;
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n - 1; i++) {
            dist[i] = Long.parseLong(stk.nextToken());
        }
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            dosi[i] = Long.parseLong(stk.nextToken());
        }

        long min = Long.MAX_VALUE;
        for (int i = 0; i < n-1; i++) {
            min = Math.min(min, dosi[i]);
            total_cost += min*dist[i];
        }
        bw.write(total_cost+"\n");

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

 

 

 

D. 쉬운 계단 수 BOJ 10844

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

난이도	Silver 1
풀이 시간	30 분
분류	2차원 DP
시간복잡도	O(N)
공간복잡도	O(101x10)

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

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 n = Integer.parseInt(br.readLine());

        long[][] dp = new long[101][10];

        dp[1][0] = 0;
        for (int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j + 1] % 1000000000;
                } else if (j == 9) {
                    dp[i][j] = dp[i - 1][j - 1] % 1000000000;
                } else { // j : 1~8
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
                }
            }
        }
        long ans = 0;
        for (int i = 0; i <= 9; i++) {
            ans += (dp[n][i] % 1000000000);
        }

        bw.write(ans%1000000000 + "\n");

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