[11월 3주차] 알고리즘 스터디

1. 호석이 두 마리 치킨 -  골드 5

출처 - https://www.acmicpc.net/problem/21278

21278번: 호석이 두 마리 치킨

 

 Sol)  스터디원 jm - 플로이드 워셜

<hide/>
public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int M;
    static int[][] graph;
    static int ans = Integer.MAX_VALUE;
    static int[] ansArr = new int[]{1,2};
    static int INF = 999999999;

    public static void main(String[] args) throws Exception{
        input();
        calcDistance(); // 모든 정점까지 거리 구하기
        // i, j번째 치킨집 차리고
        for (int i = 1; i <= N-1; i++) {
            for (int j = i+1; j <= N; j++) {
                // temp는 i번 j번에 치킨집이 있을때 이동 경로의 합
                int temp = solve(i, j);
                if (temp < ans) {
                    ansArr = new int[]{i, j};
                    ans = temp;
                }
            }
        }

        System.out.println(ansArr[0] + " " + ansArr[1] + " " + ans);
    }

    private static int solve(int i, int j) {
        int sum = 0;
        for (int x = 1; x <= N; x++) {
            int temp = Math.min(graph[x][i], graph[x][j]);
            sum += temp * 2;
        }
        return sum;
    }

    private static void calcDistance() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }

    // BFS가 아니라 벨만 포드인가 ? 그거 써야 되는구만;
    private static void input() throws Exception{
        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new int[N+1][N+1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(bufferedReader.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) continue;
                if (graph[i][j] != 1) {
                    graph[i][j] = INF;
                }
            }
        }
    }
}

 

• 한 점 기준(다익스트라), 모든 점(플로이드 워셜)의 거리를 구하는데 빠르다.
•  백준 문제는 input() 메서드를 따로 빼는 게 좋다.
• 플로이드 워셜 
  • 먼저, graph를 만들고 대각선을 제외하고 모두 INF로 세팅한다.
  • 여기에서 INF를 MAX_VALUE로 설정하면 안 된다.
  • 이유는?

 

• 입출력 예시

<hide/>
[입력]
5 4
1 3
4 2
2 5
3 2

[출력]
1 2 6

 

 

 

2. 스티커 - 실버 1

 

  출처 - https://www.acmicpc.net/problem/9465

9465번: 스티커

 

  Sol) DP - 1652ms

• 처음에는 그리디라고 생각했지만 그리디는 순간 순간의 최적해를 구하기 때문에 이 문제에서는 오답이 생길 수 있다.
• 따라서, DP로 푸는 것이 정확한 방법이다. 
• 문제의 규칙을 파악하는데 20분 정도 걸렸다.
  • 맨 앞 열, 맨 마지막 열 중에는 반드시 한 칸이 들어가야한다.
  • 대각선에 있는 두 칸을 가져오거나 2열 앞 부분에서  대각선 방향에 있는 한 칸을 가져와서 자기 자리에 있는 값을 더해준다. 
  • for문 안에 있는 식이 위의 규칙이 적용된 것이다. 
• 그리고 배열의 두 번째 열을 반드시 세팅해준 다음에 for문을 돌려야한다. 첫 번째 열은 상관 없다.
• 채점도 5분(?)은 걸린다.

<hide/>
import java.util.Scanner;

public class Test2 {

    public static int solution(int[][] dp) {

        int col = dp[0].length;

        if (col == 1) {
            return Math.max(dp[0][0], dp[1][0]);
        }
        if (col == 2) {
            return Math.max(dp[0][0] + dp[1][1], dp[1][0] + dp[0][1]);
        }

        dp[0][1] += dp[1][0];
        dp[1][1] += dp[0][0];

        for (int i = 2; i < col; i += 1) {

            dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + dp[0][i];
            dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + dp[1][i];
        }

        return Math.max(dp[0][col - 1], dp[1][col - 1]);  
    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        for (int i = 0; i < n; ++i) {
            int col = scan.nextInt();
            int[][] arr = new int[2][col];

            for (int x = 0; x < 2; ++x) {
                for (int y = 0; y < col; ++y) {
                    arr[x][y] = scan.nextInt();
                }
            }

            System.out.println(solution(arr));
        }
    }

}

 

  연습) 

• 왜 통과가 안되는지 모르겠다..
• for문에서 i = 2 부터 시작해서 2씩 증가시키면  col 개수가 홀수인 경우만 따지게 된다.
  • 따라서 if문에 i == col 인 경우를 넣어줬다.
  • 반환도 잘 되고 예외 처리도 했는데 에러도 아니고 오답이 뜨는 이유를 모르겠다.
  • 이유: 열의 개수가 홀수 개인 경우에는 맞는데 열의 개수가 짝수 개인 경우에 맨 마지막에서 두 번째 열은 포함되지 않을 수도 있다. 그런데 이 로직에서는 맨 마지막에서 두 번째 열을 반드시 포함했기 때문에 틀렸다.
  • 그래서 for문에서 i가 1 증가할 때마다 업데이트 되도록 위에 솔루션처럼 로직을 바꿨다.

<hide/>
public class Test2 {

    public static int solution(int[][] dp) {

        int col = dp[0].length;

        if (col == 1) {
            return Math.max(dp[0][0], dp[1][0]);
        }
        if (col == 2) {
            return Math.max(dp[0][0] + dp[1][1], dp[1][0] + dp[0][1]);
        }

        for (int i = 2; i <= col; i += 2) {

            if (i >= col) {
                return Math.max(dp[0][col - 1] + dp[1][col - 2], dp[1][col - 1] + dp[0][col - 2]);
            }

            dp[0][i] += Math.max(dp[1][i - 1] + dp[0][i - 2], dp[1][i - 2]);
            dp[1][i] += Math.max(dp[0][i - 1] + dp[1][i - 2], dp[0][i - 2]);
        }
        
        return Math.max(dp[0][col - 1], dp[1][col - 1]);
    }


    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        for (int i = 0; i < n; ++i) {
            int col = scan.nextInt();
            int[][] arr = new int[2][col];

            for (int x = 0; x < 2; ++x) {
                for (int y = 0; y < col; ++y) {
                    arr[x][y] = scan.nextInt();
                }
            }

            System.out.println(solution(arr));
        }
    }

}

 

 

 

3. 행복 유치원 - 골드 5

출처 - https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

 

  MySol)

<hide/>
public class Test3 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        int n = scanner.nextInt();  // n명
        int k = scanner.nextInt();  // k개의 조
        int arr[] = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = scanner.nextInt();     // [3, 6, 7, 11, 15, 18, 20]
        }
        for (int i = 0; i < n - 1; i++) {
            pq.add(arr[i + 1] - arr[i]);  // 각 차잇값을 배열로 만든다.
            // [3, 1, 4, 4, 3, 2] => [4, 4, 3, 3, 2, 1]
        }

        int ans =
            arr[arr.length - 1] - arr[0]; // 위에서 구한 모든 차잇값의 합은 결국 (arr의 최댓값) - (arr의 최솟값) 과 같다.
        for (int i = 0; i < k - 1; ++i) {
            ans -= pq.poll();       // poll()한 값이 위치한 곳에서 조가 갈라진다.
        }
        System.out.println(ans);
        
    }
}

• 스터디원의 코드를 보고 이해해서 새롭게 만들었다.
• 예를 들어,
  • ex) n = 7, k = 4, [3, 6, 7, 11, 15, 18, 20] 이라고 했을 때, 
  • 각 차잇값은 [3, 1, 4, 4, 3, 2] 이다. (차잇값의 합은 = 20 - 3)
  • 만약 여기에서 4개의 조로 나누고 싶다면  차이값 배열에서 가장 큰 3개를 선택한다.
  • 그리고 3, 1, 4, 4, 3, 2 - (가장 큰 세 개인 4, 4, 3) = > 3, 1, 2 => 6이 된다. 
• 다른 예
  •  ex) n = 7, k = 2, [3, 6, 7, 11, 15, 18, 20]  라고 하면
  • 두 개의 조로 나누면 된다. 따라서 차잇값 [3, 1, 4, 4, 3, 2] 중에서 가장 큰 한 개(4)를 뽑아 4가 위치한 7 <-> 11 사이에서 조를 가를 수 있다. 
  • 3, 1, 4, 4, 3, 2 - (가장 큰 한 개인 4) = > 3, 1, 4, 3, 2 => 13이 된다.
• 결론: (arr 최댓값) - (arr 최솟값)  

 

 

  Sol) 스터디원 ian  -  PriorityQueue

<hide/>
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int[] heights = new int[N];
		for (int i = 0; i < N; i++) {
			heights[i] = Integer.parseInt(st.nextToken());
		}
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for (int i = 0; i < N - 1; i++) {
			pq.add(heights[i + 1] - heights[i]);
		}
		int answer = 0;
		for (int i = 0; i < N - P; i++) {
			answer += pq.poll();
		}
		System.out.println(answer);
	}
}

• 1 3 5 6 10 이라고 주어졌을 때, (n = 5, m = 3)
  • 각 숫자간의 차이는 2 2 1 4 이다.
  • 이 데이터를 오름차순으로 바꾸면 1 2 2 4
  • 여기에서 n - m개만 poll()해서 더해주면 답이 된다.
  • 왜 n - m개일까?
  • 1을 뽑으면 (5, 6)은 한 조가 되고 다음으로 2를 뽑으면 (1, 3)이 한 조가 된다. 
  • 따라서 뽑는 횟수에 1을 더한 만큼 조가 구성된다. 
    • 그러면 남아있는 5는 저절로 조가 구성되니까 결국 n-m 번만 뽑으면 되는 것이다.
    • 1 3 / 5 6 / 10

 

 

4. 수들의 합 - 실버 5

출처 - https://www.acmicpc.net/problem/1789

1789번: 수들의 합

 

  MySol) 근의 공식 - 124ms

<hide/>
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        long s = Long.parseLong(str);
        double ans = (double) (Math.sqrt(1 + 8 * s) - 1) / 2;
        System.out.println((int) (ans / 1));
    }
}

• 1 부터 n까지 모든 수들의 합 s 
  
  • n(n + 1) / 2 = s
  • n^2 + n - 2s = 0
  • 근의공식 => n = {-1 + 루트(1 + 8s)} / 2
• 서로 다은 N개의 자연수의 합이 S일 때, N이 최댓값이 되도록 하려면?
  • 최대한 적은 수들로 구성해야 개수 N이 최대가 될 수 있다. 
  • 따라서, 1 + 2+ 3 + ... + (어떤 수) 까지의 합이 S와 근접할 것이다. 
  • 예를 들어, S = 200일 때,
    • 1 + 2 + 3 + ... + 19 = 190
    • 1 + 2+ 3 + ... + 20 = 210
    • => 1 + 2+ 3 + ... + 19 + 10 = 200이 가능하다. 
    • 따라서, n(n + 1) / 2 = 200으로 두고 방정식을 푼다. 
    • n = {-1 + 루트(8s + 1)} / 2
    • 그 다음, n을 내림하면 답이 된다.

 

  Sol) 스터디원 코드(GH) - 128ms

• 내 코드랑 구성이 좀 다른데 Math.sqrt() 를 쓰나 아래 코드처럼 for문을 이용해서 모두 더하나 속도는 큰 차이가 없다.
• 근의 공식같은 걸 쓰지 않는 다면 아래 코드가 이해하기 쉬운 편인 것 같다.

<hide/>
public class Main {
    public static int solution(int S) {
        int cnt = 0;
        int sum = 0;
        for (int i = 1; i <= S; i++) {
            sum += i;
            cnt++;

            if (sum > S) {
                cnt--;
                break;
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int S = Integer.parseInt(br.readLine());
        System.out.print(solution(S));
    }
}

 

 

 

5. 숫자 카드 - 실버 5

출처 - https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

  Sol) 스터디원 코드(gh) - 이진 탐색 

<hide/>
public class Main {
    public static void solution(int[] myCard, int[] yourCard) {
        int[] result = new int[yourCard.length];

        Arrays.sort(myCard);

        for (int i = 0; i < yourCard.length; i++) {
            int left = 0;
            int right = myCard.length - 1;

            while (left <= right) {
                if (myCard[left] == yourCard[i]) {
                    result[i] = 1;
                }
                if (myCard[right] == yourCard[i]) {
                    result[i] = 1;
                }

                int mid = (left + right) / 2;
                if (yourCard[i] == myCard[mid]) {
                    result[i] = 1;
                    break;
                } else if (yourCard[i] < myCard[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }

        Arrays.stream(result).forEach(x -> System.out.print(x + " "));
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] NArr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < NArr.length; i++) {
            NArr[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());

        int[] MArr = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < MArr.length; i++) {
            MArr[i] = Integer.parseInt(st.nextToken());
        }

        solution(NArr, MArr);
    }
}

 

 

 

6. 경로 찾기 - 실버 1

 

출처 - https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

  MySol) 삼중 for문 - 224ms

<hide/>
public class Test1 {

    public static void solution(int[][] graph, int n) throws IOException {
        if(n == 1){
            System.out.println(graph[0][0]);
            return;
        }
        int[][] result = method(graph, n);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int[] row : result) {
            for (int r : row) {
                bw.write(r + " ");
            }
            bw.write("\n");
        }
        bw.close();
    }

    public static int[][] method(int[][] graph, int n) {
        // [1][2] & [2][3] = > [1][3] 가능
        for (int i = 0; i < n; ++i) {      // 새로운 열
            for (int j = 0; j < n; ++j) {

                if (graph[i][j] == 1) {
                    for (int k = 0; k < n; ++k) {  //새로운 행
                        if (graph[k][i] == 1) {
                            graph[k][j] = 1;
                        }
                    }
                }
            }
        }
        return graph;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] graph = new int[n][n];

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

• 단방향 매핑
• [i][j] , [k][i] = 1인 경우에 k에서 j로도 갈 수 있다는 성질을 이용한다.
• 처음에는 while문을 돌려서 여러 번 실행해야 한다고 생각했는데 돌려보니까 한 번만 실행해도 답이 나온다.
  • 이유를 정확히 모르겠다.
• BufferedReader, BufferedWriter을 쓰면 속도가 훨씬 빨라진다.
• BufferedWriter를 쓰면 반드시 close() 로 닫아줘야 정상 출력이 된다.

 

  Sol) 스터디원 코드(GH) - 232ms

<hide/>
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][N];

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

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1) {
                    for (int k = 0; k < N; k++) {
                        if (arr[k][i] == 1) {
                            arr[k][j] = 1;
                        }
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                bw.write(arr[i][j] + " ");
            }
            bw.write('\n');
        }

        bw.close();
        br.close();
    }

}

• 내 코드랑 거의 비슷하다.

 

  Sol) 스터디원 코드(jy) - DFS 

<hide/>

public class BOJ {

    static int size;
    static int[][] grid;
    static int[][] out;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        size = Integer.parseInt(st.nextToken());
        grid = new int[size][size];
        out = new int[size][size];

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

        solution();

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                System.out.print(out[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void solution() {
        for (int i = 0; i < size; i++) {
            visited = new boolean[size];
            for (int j = 0; j < size; j++) {
                if(grid[i][j] == 1) {
                    visited[j] = true;
                    int rowIdx = j;
                    out[i][j] = 1;
                    recur(rowIdx, i);
                }
            }
        }
    }

    public static void recur(int rowIdx, int rootIdx) {
        for (int i = 0; i < size; i++) {
            if(grid[rowIdx][i] == 1 && !visited[i]) {
                out[rootIdx][i] = 1;
                visited[i] = true;
                recur(i, rootIdx);
            }
        }
    }
}

 

 

 

 

7. DFS와 BFS - 실버 2

출처 - https://www.acmicpc.net/problem/1260

 

   MySol) 1차원 DFS, BFS - 668ms

<hide/>
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Test5 {

    static int[][] graph;
    static boolean[] visited;

    static Queue<Integer> queue = new ArrayDeque<>();

    public static void dfs(int currNode) {

        visited[currNode] = true;
        System.out.print(currNode + " ");
        for (int nextNode = 1; nextNode < graph.length; ++nextNode) {
            if (!visited[nextNode] && graph[currNode][nextNode] == 1) {
                dfs(nextNode);
            }
        }
    }

    public static void bfs(int startNode) {

        visited[startNode] = true;
        queue.add(startNode);
//        System.out.println("start " + startNode + " dis: " + dis);
        System.out.print(startNode + " ");

        while (!queue.isEmpty()) {
            int currNode = queue.poll();

            for (int nextNode = 1; nextNode < graph.length; ++nextNode) {
                if (graph[currNode][nextNode] == 1 && !visited[nextNode]) {
                    visited[nextNode] = true;
                    queue.add(nextNode);
//                    System.out.println("next " + nextNode + " dis: " + dis);
                    System.out.print(nextNode + " ");

                }
            }
        }
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int node = scanner.nextInt();
        int edge = scanner.nextInt();
        int startNode = scanner.nextInt();
        graph = new int[node + 1][node + 1];
        visited = new boolean[node + 1];

        for (int i = 0; i < edge; ++i) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            graph[start][end] = 1;
            graph[end][start] = 1;
        }

        dfs(startNode);
        System.out.println();
        visited = new boolean[node + 1];
        bfs(startNode);

    }
}

• 기본적인 BFS, DFS 1차원 유형이다.

 

 

8. 벽 부수고 이동하기 - 골드 3

 출처 - https://www.acmicpc.net/problem/2206

 

  Sol) 스터디원 코드(jy) - 1600ms

<hide/>
public class Main {

    public static int N;
    public static int M;
    public static int[][] map;
    public static final int[][] dir = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    public static PriorityQueue<Here> pq;
    public static int[][] visited;
    public static int answer = Integer.MAX_VALUE;

    public static class Here implements Comparable<Here> {
        int x;
        int y;
        int block;
        int count;

        public Here(int x, int y, int block, int count) {
            this.x = x;
            this.y = y;
            this.block = block;
            this.count = count;
        }

        @Override
        public int compareTo(Here o) {
            return this.count >= o.count ? 1 : -1;
        }
    }

    public static void main(String[] args) throws IOException {
        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];
        visited = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String[] s = st.nextToken().split("");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(s[j]);
                visited[i][j] = Integer.MAX_VALUE;
            }
        }
        pq = new PriorityQueue<>();
        Here start = new Here(0, 0, 0, 1);
        visited[start.x][start.y] = 0;
        pq.add(start);
        while(!pq.isEmpty()) {
            Here now = pq.poll();
            if(now.x == N - 1 && now.y == M - 1) {
                System.out.println(now.count);
                return;
            }
            for (int[] d : dir) {
                int x = now.x + d[0];
                int y = now.y + d[1];
                if (x >= 0 && y >= 0 && x < N && y < M) {
                    if(visited[x][y] > now.block) {
                        if(map[x][y] == 0) {
                            pq.add(new Here(x, y, now.block, now.count + 1));
                            visited[x][y] = now.block;
                        } else {
                            if(now.block == 0) {
                                pq.add(new Here(x, y, now.block + 1, now.count + 1));
                                visited[x][y] = now.block + 1;
                            }
                        }
                    }
                }
            }
        }
        System.out.println(-1);
    }
}

• 기존에 제로베이스에서 봤던 코테 문제와 유사하다
  • 그 때는 visited 배열을 3차원으로 선언해서 풀었다.
• 3차원 배열없이 풀기 위해 새벽까지 고민하시더나 결국  위 방법으로 푸셨다.

 

  입출력)

<hide/>
6 4
0100
1110
1000
0000
0111
0000

15


4 4
0111
1111
1111
1110

-1