이것저것 개발 블로그

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_BJ_11650_좌표정렬하기 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<int []> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0])
                    return o1[1]-o2[1];
                return o1[0]-o2[0];
            }
        });
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            pq.offer(new int[] {x, y});
        }


        for(int i=0; i<n; i++){
            int[] cur = pq.poll();
            System.out.println(cur[0] +" "+cur[1]);
        }
    }//main
}

정렬만 하면 되는 문제이다.

나는 priorityQueue를 사용했지만, Arrays.sort를 이용하는 방법도 있다.

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main_BJ_2667_단지번호붙이기 {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int cnt, house, n;
    static PriorityQueue<Integer> houses = new PriorityQueue<>();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visited = new boolean[n][n];

        for(int i=0; i<n; i++){
            String str = br.readLine();
            for(int j=0; j<n; j++){
                map[i][j] = str.charAt(j) - '0';
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] == 1 && !visited[i][j]) {
                    house = 1;
                    cnt++;
                    dfs(i, j);
                    houses.add(house);
                }
            }
        }

        System.out.println(cnt);
        int size = houses.size();
        for(int i=0; i<size; i++)
            System.out.println(houses.poll());
    }//main
    private static void dfs(int x, int y){
        visited[x][y] = true;

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(check(nx, ny) && !visited[nx][ny] && map[nx][ny] != 0){
                house++;
                dfs(nx, ny);
            }
        }

    }//dfs

    private static boolean check(int x, int y){
        if(x<0 || y<0 || x>=n || y>=n)
            return false;
        return true;
    }//check
}

완탐으로 가면 좋을것 같아서 시작했다.

dfs, bfs어느것도 상관이 없을 것 같지만 최근에 bfs로 문제를 많이 풀어본 것 같아서 dfs를 이용해서 해봤다.

전체 단지 수 변수를 만들고, 해당 단지를 오름차순으로 저장하기 위해 Priority Queue를 사용해서 풀었다.

그런데,, 마지막 출력할때 queue를 poll하면 사이즈 줄어들어서 모두 출력 안되는 사실을 자꾸 까먹어서 웨않되를 자꾸 외치는 바보...

그래프 문제를 풀어보기에 간단하고 괜찮은 문제~~

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main_BJ_11286_절댓값힙 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if(Math.abs(o1) == Math.abs(o2))
                    return o1-o2;
                else
                    return Math.abs(o1)-Math.abs(o2);
            }
        });

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            int num = Integer.parseInt(br.readLine());
            if(num == 0 && pq.isEmpty()){
                sb.append(0+"\n");
            }
            else if(num==0 && !pq.isEmpty()){
                sb.append(pq.poll() +"\n");
            }
            else
                pq.offer(num);
        }
        System.out.println(sb);
    }//main
}

Priority Queue에서 정렬 기준을 comparator로 설정할 수 있음을 기억하자!!!

나머지는 조건에 따라 작업해주기만 하면 되어서...

끝!!

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

풀이)

import java.util.Map;
import java.util.Scanner;

public class Main_BJ_17626_FourSquares {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        /*
            1 1       => 1
            2 1+1     => 1
            3 1+1+1   => 1
            4 2       => 1
            5 2+1     => 2
            6 2+1+1   => 2
            7 2+1+1+1 => 2
            8 2+2     => 1
            9 3       => 1
            10 3+1    => 2
            11 3+1+1  => 2
            12 3+1+1+1 => 2
            13 3+2    =>2
            14 3+2+1  => 3
            15 3+2+1+1 => 3
            16 4       => 1
            17 4+1     => 2
           ...
           dp[i] = min(dp[i-j*j])+1
           어떤수 i 최적해 =>
            i보다 작은 모든 제곱수들 중 i-제곱수를 한 해 중 가장 작은 해 + 1

         */

        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for(int j=1; j*j<=i; j++){
               min = Math.min(min, dp[i-j*j]);
            }
            dp[i]=min+1;
        }
    System.out.println(dp[n]);
    }//main
}

규칙찾는데 어려웠다.. 수학으로 생각해야했던 문제였던것 같음

다시 풀어봐야징...

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main_BJ_9461_파도반수열 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int tc = 1; tc<=t; tc++){
            int n = Integer.parseInt(br.readLine());
            long[] dp = new long[n+1];
            dp[1] = 1;
            if(n>3) {
                dp[2] = 1;
                dp[3] = 1;

                for (int i = 4; i <= n; i++)
                    dp[i] = dp[i - 2] + dp[i - 3];
            }
            else if(n>2){
                dp[2] = 1;
                dp[3] = 1;
            }
            else if(n>1)
                dp[2] = 1;

            System.out.println(dp[n]);
        }//tc
    }//main
}

문제에 나와있듯이 규칙은 쉽다. (dp[i] = dp[i-2]+dp[i-3])

다만, 다른 문제와 달리 나머지를 더해나가는 것이 아니라, 그냥 모조리 더하는 것이기 때문에 long 타입으로 선언해줘야한다!

이부분을 깜박함...ㅠ

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BJ_14500_테트로미노 {
    static int[][] map;
    static int max, n, m;
    static int[] dx = {-1, 1, 0 ,0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        boolean[][] visited = new boolean[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                visited[i][j] = true;
                dfs(i, j, 0, 0, visited);
                visited[i][j] = false;
                shape(i, j);
            }
        }

        System.out.println(max);

    }//main
    private static void dfs(int x, int y, int cnt, int sum, boolean[][] visited){
        if(cnt == 4) {
            max = Math.max(max, sum);
            return;
        }

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(check(nx, ny) && !visited[nx][ny]){
                visited[nx][ny] = true;
                dfs(nx, ny, cnt+1, sum+map[x][y], visited);
                visited[nx][ny] = false;
            }
        }
    }//dfs

    private static boolean check(int x, int y){
        if(x<0 || y<0 || x>=n || y>=m)
            return false;
        return true;
    }//check

    private static void shape(int x, int y){
        if(x<n-2 && y<m-1)
            max = Math.max(max, map[x][y]+map[x+1][y]+map[x+2][y]+map[x+1][y+1]);

        if(x<n-2 && y>0)
            max = Math.max(max, map[x][y]+map[x+1][y]+map[x+2][y]+map[x+1][y-1]);

        if(x>0 && y<m-2)
            max = Math.max(max, map[x][y]+map[x][y+1]+map[x][y+2]+map[x-1][y+1]);

        if(x<n-1 && y<m-2)
            max = Math.max(max, map[x][y]+map[x][y+1]+map[x][y+2]+map[x+1][y+1]);

    }//shape
}

시간초과 때문에 조금 힘들었다.

1. ㅗ 모양을 제외하고는 dfs로 구하기 간단해서 구했다.

2. ㅗ 모양을 구하기 위해 shape이라는 함수를 따로 만들어서 구현해줬다.(x, y 기준으로 범위를 넘지 않게끔 잡아준 후 더하면 된다)

하지만 시간초과..

찾아보니 전역변수를 많이 설정해도 참조하는데 시간이 오래 걸리기 때문에 지역변수로 바꾸려고 했다.

따라서 boolean[][] 함수를 지역변수로 만들었지만, 탐색할때마다 생성하게 했더니,, 그것도 시간이 오래 걸려서..(생각해보면 당연함)

dfs 돌리기 전 후로 true, false 값을 바꿔주는 것으로 변경했다!!

좀 더 생각해보면 좋았을텐데 아쉬운 문제였다.

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BJ_1780_종이의개수 {
    static int[][] paper;
    static int plus, zero, minus;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        paper = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        devide(0, 0, n);
        System.out.println(minus);
        System.out.println(zero);
        System.out.println(plus);

    }//main
    private static void devide(int x, int y, int size){
        int num = paper[x][y];
        for(int i=x; i<x+size; i++){
            for(int j=y; j<y+size; j++){
                if(num != paper[i][j]){
                    devide(x, y, size/3);
                    devide(x, y+size/3, size/3);
                    devide(x, y+size/3*2, size/3);

                    devide(x+size/3, y, size/3);
                    devide(x+size/3, y+size/3, size/3);
                    devide(x+size/3, y+size/3*2, size/3);

                    devide(x + size/3*2, y, size/3);
                    devide(x + size/3*2, y+size/3, size/3);
                    devide(x + size/3*2, y+size/3*2, size/3);

                    return;
                }
            }
        }

        if(num == -1)
            minus++;
        else if(num == 0)
            zero++;
        else
            plus++;
    }//devide
}

이번에도 재귀문제!

다만 달라진 점은 무조건 9개로 쪼개야 해서 나눠야 할게 많다는 점이다.

또한 나누고 난 다음엔 무조건 return을 해야한다는점!

for문을 다 통과하면 종이에 적힌 숫자대로 개수를 늘려주면 끝!!

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BJ_11403_경로찾기 {
    static int[][] adj;
    static int n;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        adj = new int[n][n];
        int[][] ans = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                adj[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(route(i, j))
                    ans[i][j] = 1;
                else
                    ans[i][j] = 0;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                sb.append(ans[i][j]+" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }//main
    private static boolean route(int start, int end){
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);
//        visited[start] = true;

        while(!q.isEmpty()){
            int cur = q.poll();
            for(int i=0; i<n; i++){
                if(adj[cur][i]==1 && !visited[i]){
                    q.add(i);
                    visited[i] = true;
                }
            }
        }

        if(visited[end])
            return true;
        return false;
    }//route
}

이 문제가 플로이드-워셜 문제인걸 풀고 나서 알았다...

다시 공부해서 올려야징

나는 플로이드로 풀진 않았고, bfs랑 비슷한 논리를 사용해서 했다.

이때, 주의할점은 start == end 일 수 있으므로, 큐에 처음 넣을 때 방문처리를 하지 않아야 한다.

또한 queue에서 꺼낸 값 cur이 end와 같다해서 바로 true를 리턴하면 안된다...

처음엔 당연히 출발==도착이면 방문할 수 있을줄 알았다ㅋㅋㅋ

풀이2) 플로이드-워셜 알고리즘

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BJ_11403_경로찾기 {
    static int[][] adj;
    static int n;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        adj = new int[n][n];
        int[][] ans = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                adj[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //단순히 가는 것만 체크
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(adj[i][k] == 1 & adj[k][j]==1)
                        adj[i][j] = 1;
                }
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                System.out.print(adj[i][j]+" ");
            }
            System.out.println();
        }

    }//main
}

이 문제는 플로이드 워셜로 풀면 훨씬 시간이 단축된다.

애초에 간선에 가중치도 없었고, 문제 자체도 연결 되었는지 아닌지만 파악하면 되기 때문!

따라서 adj[i][k] == 1 && adj[k][j]==1의 조건만 있으면 된다.

플로이드-워셜 간단 정리

• 모든 정점에서 모든 정점까지의 최단 거리를 구할 때 사용
• 음수 사이클이 없어야함
• 인접행렬 이용
  • 본인과 본인의 거리는 최소 0이라고 판단
  • 본인과 연결되지 않은 정점은 최대로 넣어줌
• 차례대로 정점을 1개 거치고,,, 2개 거치고,,, n개를 거치는 경우가 가능함. 
  • 즉, 바로 연결된 정점을 가느냐 vs k 정점을 거쳐서 가느냐(이것 또한 계속 갱신된것)
  • adj[i][j] = Math.min(adj[i][j], adj[i][k]+adj[k][j])와 같음

참고한 블로그는 다음과 같다.

https://sskl660.tistory.com/61

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main_BJ_9375_패션왕신해빈 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int tc = 1; tc<=t; tc++){
            int n = Integer.parseInt(br.readLine());
            Map<String, Integer> clothes = new HashMap<>();
            int ans = 1;

            for(int i=0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String name = st.nextToken();
                String type = st.nextToken();
                if(clothes.containsKey(type))
                    clothes.put(type, clothes.get(type)+1);
                else
                    clothes.put(type, 1);
            }

//          (종류 + 1) * (종류 + 1) ... -1
            for(int value : clothes.values())
                ans *= value+1;

            System.out.println(ans-1);
        }//test case
    }//main
}

문제를 풀기엔 간단했다. 수학문제 느낌!

해당 옷을 입고, 안 입고의 경우의 수가 있으므로, 1을 더해준 후, 경우의 수를 모두 곱해준다.

이후 옷을 아예 안 입을 수 있으므로 1을 빼준다면 끝!

나는 해시에 옷을 모두 저장해서 가지수를 세려고 했는데,,,

그럴필요없이 그냥 개수를 저장하면 되는것,,,,

바보였다.

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

풀이)

import java.util.Scanner;

public class Main_BJ_11727_2xn타일링2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n];

        /*
        1 => 1
        2 => 3
        3 => 5
        4 => 11
         */

        dp[0] = 1;
        if(n>1)
            dp[1] = 3;

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

        System.out.println(dp[n-1]);
    }//main
}

경우의 수를 잘 못세서,,, 규칙 못찾았다..

다시...풀어야징...

쉽게 생각하면, 경우의 수가 늘어날 때, 양 옆에 2x1타일이 붙는 것을 볼 수 있다.

검색해보면 친절하게 설명한 블로그가 있으니 참고하길 바란다.