[백준 7568/1904/1018/25682/2110] 자바

(title: [백준 7568/1904/1018/25682/2110] 자바)

A. 덩치 BOJ 7568 

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

7568번: 덩치

난이도	Silver 5
풀이 시간	9 분
분류	브루트포스, 구현
시간복잡도	O(N^2)
공간복잡도	O(50+50)

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


public class Main {
    private static class info {
        int w;
        int h;
        int idx;

        public info(int w, int h) {
            this.w = w;
            this.h = h;
        }
    }

    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());
        info[] arr = new info[n];
        int[] rank = new int[n];

        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(stk.nextToken());
            int h = Integer.parseInt(stk.nextToken());
            arr[i] = new info(w,h);
        }
        for(int i = 0 ; i < n ; i++){
            int cnt = 0;
            info now = arr[i];
            for(int j = 0; j<n; j++){
                info cur = arr[j];
                if(now.w<cur.w&&now.h<cur.h){
                    cnt++;
                }
            }
            rank[i] = cnt+1;
        }

        for(int i = 0; i <n; i++){
            bw.write(rank[i]+" ");
        }

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

 

 

B. 01타일 BOJ 1904

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

1904번: 01타일

난이도	Silver 3
풀이 시간	20 분
분류	DP
시간복잡도	O(N)
공간복잡도	O(1000000)

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());
        final int mod = 15746;
        long [] dp = new long[n+1];

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

        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i<=n; i++){
            dp[i] = (dp[i-1] + dp[i-2])%mod;
        }

        bw.write((dp[n])%mod+"\n");


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

 

 

 

C. 체스판 다시 칠하기 BOJ 1018

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

1018번: 체스판 다시 칠하기

난이도	Silver 4
풀이 시간	50 분
분류	구현
시간복잡도	O(N^4)
공간복잡도	O(50*50)

 

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


public class Main {
    static int n;
    static int m;
    static int[][] board;
    static final int black = 1;
    static final int white = 0;

    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 row = Integer.parseInt(stk.nextToken());
        int col = Integer.parseInt(stk.nextToken());


        board = new int[row][col];
        for (int i = 0; i < row; i++) {
            char[] in = br.readLine().toCharArray();
            for (int j = 0; j < col; j++) {
                if (in[j] == 'W') {
                    board[i][j] = 0;
                } else {
                    board[i][j] = 1;
                }
            }
        }

        int count = 0; int ans = Integer.MAX_VALUE;
        for (int i = 0; i < row-7; i++) {
            for (int j = 0; j < col-7; j++) { // 시작점 탐색
                // (j, i) 에 대하여
                count = 0;

                int leftTop = board[i][j];
                for (int y = i; y < i + 8; y++) {
                    for (int x = j; x < j + 8; x++) {
                        if((x+y)%2==0){
                            // leftTop 과 색이 동일해야함
                            if(leftTop != board[y][x]){
                                // 근데 다르면?
                                count++;
                            }
                        } else{
                            // leftTop 과 색이 달라야 함
                            if(leftTop==board[y][x]){
                                // 근데 같으면?
                                count++;
                            }
                        }
                    }
                }


                int rev = 64-count;

                ans = Math.min(Math.min(count, rev), ans);
            }
        }
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
    }
}

 

 

D. 체스판 다시 칠하기2 BOJ 25682

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

25682번: 체스판 다시 칠하기 2

난이도	Gold 5
풀이 시간	50 분
분류	누적합
시간복잡도	O(NM)
공간복잡도	O(2000*2000*2)

 

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


public class Main {
    static int [][] dp;
    static int[][] board;
    static int row;
    static int col;
    static int k;

    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());
        row = Integer.parseInt(stk.nextToken());
        col = Integer.parseInt(stk.nextToken());
        k = Integer.parseInt(stk.nextToken());

        board = new int[row][col];

        for (int i = 0; i < row; i++) {
            char[] in = br.readLine().toCharArray();
            for (int j = 0; j < col; j++) {
                board[i][j] = in[j];
            }
        }

        int ans = Math.min(getCnt('W'), getCnt('B'));

        bw.write(ans+"\n");
        bw.flush();
        bw.close();
    }
    private static int getCnt(int color){
        dp = new int[row+1][col+1];
        int ret = Integer.MAX_VALUE;
        int val = 0;
        for(int i = 0 ; i < row; i++){
            for(int j = 0 ; j < col; j++){
                if((i+j)%2==0){
                    val = color!=board[i][j] ? 1 : 0;
                } else {
                    val = color==board[i][j] ? 1 : 0;
                }
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + val;
            } // calc 2-d prefix
        }

        for(int i = 1 ; i <= row-k+1; i++){
            for(int j = 1; j <= col-k+1; j++){
                ret = Math.min(ret, dp[i+k-1][j+k-1] - dp[i+k-1][j-1] - dp[i-1][j+k-1] + dp[i-1][j-1]);
            }
        }

        return ret;
    }
}

 

E. 공유기 설치 BOJ 2110

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

2110번: 공유기 설치

난이도	Gold 4
풀이 시간	20분
분류	parametric search, 이분 탐색
시간복잡도	O(nlogn)
공간복잡도	O(200000)

import java.io.*;
import java.util.Arrays;
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;

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

        int[] house = new int[n];
        for (int i = 0; i < n; i++) {
            house[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(house);

        int low = 1;
        int high = house[n - 1] - house[0] + 1;
        int mid = 0;
        int cnt = 0;


        while (low < high) {
            mid = (low + high) / 2;
            cnt = getCnt(mid, house); // mid 간격으로 설치 가능한 공유기의 개수를 계산
            if (cnt < c) {
                // mid 간격으로 설치하면, 가지고 있는 공유기보다 더 적게 설치할 수 밖에 없다면
                // 간격을 줄여야 한다.
                high = mid;
            } else {
                // mid 간격으로 설치하면, 가지고 있는 공유기를 모두 사용할 수 있거나
                // 더 필요한 상황이라면 간격을 늘려야 한다.
                low = mid + 1;
            }
        }

        bw.write((low - 1) + "\n");
        bw.flush();
        bw.close();
    }

    private static int getCnt(int diff, int[] house) {
        int ret = 0;
        int cnt = 1;
        int t = house[0];
        for (int i = 1; i < house.length; i++) {
            if (diff <= house[i] - t) {
                cnt++;
                t = house[i];
            }
        }
        return ret = cnt;
    }
}