[SWEA] 4796. 의석이의 우뚝 선 산 D4 - Simulation

제출일 : 2019-09-24

문제 풀이 시간 : 1H

난이도 : ★★☆

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2h6AKBCoDFAVT

Input

첫 번째 줄에 테스트 케이스의 수 T(1≤T≤10)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 자연수 N(3≤N≤50,000)이 주어진다.

다음 줄에는 N개의 자연수 h1,…,hN (1≤hi≤10^9)이 순서대로 공백 하나로 구분되어 주어진다.

모든 1≤i＜j≤N 에 대해 hi≠hj 이다.

Output

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 우뚝 선 산이 될 수 있는 구간의 개수를 출력하라.

Example

input

3
3
1 3 2
3
3 2 1
9
1 4 6 5 3 7 9 2 8

output

#1 1
#2 0
#3 6    

Solution & Inpression

1 2 5 3 2 1

위와 같은 경우 우뚝 선 산이 될수 있는 구간은

1 2 5 3

1 2 5 3 2

1 2 5 3 2 1

2 5 3

2 5 3 2

2 5 3 2 1

총 6가지 = 2 X 3 으로 구할수 있다.

Code

언어 : JAVA

메모리 : 102,944 kb

실행시간 : 1,584 ms

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

public class Solution {
    static int N;

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            int cnt = 0;

            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = sc.nextInt();
            }

            for (int i = 0; i < N - 2; i++) {
                int idx = i; 
                int tmp1 = 0;

                while (arr[idx] < arr[++idx]) {
                    tmp1++;
                    if (!range(idx + 1)) {
                        idx++;
                        break;
                    }
                }
                idx--;

                if (i == idx || idx == (N - 1))
                    continue;

                i = idx - 1;

                int tmp2 = 0;
                while (arr[idx] > arr[++idx]) {
                    tmp2++;
                    if (!range(idx + 1)) {
                        idx++;
                        break;
                    }
                }
                idx--;
                cnt += tmp1 * tmp2;
            }
            System.out.println("#" + tc + " " + cnt);
        }
        sc.close(); // Scanner close
    }

    static boolean range(int x) {
        if (0 <= x && x < N)
            return true;
        return false;
    }
}

[JUNGOL] 1841. 월드컵 - DFS

제출일 : 2019-10-01

문제 풀이 시간 : 1H 45M

난이도 : ★★★☆

Problem

link : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1114&sca=50&stx=%EC%9B%94%EB%93%9C%EC%BB%B5

Input

첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다.

Output

입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.

Example

input

5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4 
4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3 
5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5
5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4

output

1 1 0 0

Solution & Inpression

결과적으론 BFS를 이용하면 된다.

하지만 나는 단순하게 조건을 주어 해결하려 하였다. 하지만 계속 예외가 발생했고 생각하지 못한 조건들이 계속 발견되어 총 라인수가 150라인을 넘어가고있었다.

다시 생각을 하였다.

전체 경기는 총 15번 진행된다

A vs B C D E F
B vs C D E F
C vs D E F
D vs E F
E vs F

또한 각 경기는 3가지 경우가 존재한다

• Team1 승리 , Team2 패배
• Team1 비김 , Team2 비김
• Team1 패배 , Team2 승리

이때 시간복잡도는 O(3^15) 로 완전탐색을 진행할 수 있다.

따라서 완전탐색을 이용하여 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 16 mb

실행시간 : 1009 ms

import java.util.Scanner;

public class Main {

    static int[] team1 = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4 };
    static int[] team2 = { 1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5 };
    static int[][] matrix;
    static int[][] result;
    static int[] ans;

    static void dfs(int tc, int game) {
        if (game == 15) { // 모든 경기를 마치고
            if (ans[tc] != 1) { // 이전에 판별되지 않았다면
                // 판별시작
                for (int i = 0; i < 6; i++) {
                    for (int j = 0; j < 3; j++)
                        // 결과가 하나라도 같지 않다면
                        if (matrix[i][j] != result[i][j])
                            return;
                }

                // 경기결과가 일치한다면
                ans[tc] = 1; // 결과테이블에 저장
                return;

            } else
                return;
        }

        // ---------------------DFS--------------------- //
        // |승0|무1|패2|

        int t1 = team1[game];
        int t2 = team2[game];

       // t1 win, t2 lose
        result[t1][0]++;        result[t2][2]++;
        dfs(tc, game + 1);
        result[t1][0]--;        result[t2][2]--;

        // t1 draw, t2 draw
        result[t1][1]++;        result[t2][1]++;
        dfs(tc, game + 1);
        result[t1][1]--;        result[t2][1]--;

        // t1 lose, t2 win
        result[t1][2]++;        result[t2][0]++;
        dfs(tc, game + 1);
        result[t1][2]--;        result[t2][0]--;

    }

    public static void main(String[] args) {
        // 백준_6987_월드컵
        // 정올_1841_월드컵
        Scanner sc = new Scanner(System.in);

        matrix = new int[6][3];
        result = new int[6][3];
        ans = new int[4];

        for (int tc = 0; tc < 4; tc++) {
            for (int i = 0; i < 6; i++) {
                for (int j = 0; j < 3; j++) {
                    matrix[i][j] = sc.nextInt();
                }
            }
            dfs(tc, 0);
        }

        for (int x : ans)
            System.out.print(x + " ");
        System.out.println();

        sc.close();
    }
}

[SWEA] 1289. 원재의 메모리 복구하기 D3 - Array

제출일 : 2019-07-16

문제 풀이 시간 : 15M

난이도 : ★☆

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN

Input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 메모리의 원래 값이 주어진다.

메모리의 길이는 1이상 50이하이다.

Output

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

초기값(모든bit가 0)에서 원래 값으로 복구하기 위한 최소 수정 횟수를 출력한다.

Example

input

2
0011
100

output

#1 1
#2 2

Solution & Inpression

문제에서 초기값은 모든 비트가 0이라고 정해져있다.

오른쪽부터 현재 메모리의 값(해당 비트의 값)이 복구하고자 하는 메모리 값이 아니라면 바꾸고자 하는 값으로 현재비트부터 첫번째 비트까지 값을 바꾸어 준다.

위작업을 비트수만큼 진행한다.

Code

언어 : JAVA

메모리 : 20,540 kb

실행시간 : 138 ms

import java.util.Arrays;
import java.util.Scanner;
import java.io.FileInputStream;
import java.lang.reflect.Array;

public class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int tc = 1; tc <= T; tc++){

            char[] input = sc.next().toCharArray(); 
            char[] tmp = new char[input.length()];

            int cnt=0;

            for(int i =0 ; i<input.length();i++) {
                tmp[i]='0';
            }


            for(int i =0 ; i<input.length();i++) {
                if(input[i]!=tmp[i]) {
                    char tmpNum=input[i];
                    for(int j=i; j<input.length();j++) {
                        tmp[j]=tmpNum;
                    }
                    cnt++;
                }       
            }
            System.out.println("#" + tc + " " + cnt);
        }
    }
}

[SWEA] 1204. 최빈수 구하기 D2 - Array

제출일 : 2019-07-16

문제 풀이 시간 : 15M

난이도 : ★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV13zo1KAAACFAYh

Input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 테스트 케이스의 번호가 주어지고 그 다음 줄부터는 점수가 주어진다.

Output

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다.

Constraints

학생의 수는 1000명이며, 각 학생의 점수는 0점 이상 100점 이하의 값이다.

Example

input

10
1
41 85 72 38 80 69 65 68 96 22 49 67 51 61 63 87 66 24 80 83 71 60 64 52 90 60 49 31 23 99 94 11 25 24 51 15 13 39 67 97 19 76 12 33 99 18 92 35 74 0 95 71 39 33 39 32 37 45 57 71 95 5 71 24 86 8 51 54 74 24 75 70 33 63 29 99 58 94 52 13 35 99 46 57 71 23 17 3 94 48 77 18 83 11 83 25 59 62 2 78 86 7 94 65 80 32 39 84 60 65 72 61 58 84 8 72 12 19 47 49 49 59 71 52 34 22 21 20 92 33 80 39 74 9 28 97 100 93 29 25 4 66 79 81 98 21 91 62 82 4 59 100 34 1 51 80 92 69 77 39 38 97 51 34 35 19 22 1 67 9 90 31 82 11 51 84 78 70 74 42 100 88 53 80 57 62 32 51 48 63 92 46 4 61 31 98 69 52 88 20 68 41 48 79 97 98 56 44 73 3 63 100 87 87 41 79 64 83 63 1 21 72 24 9 75 51 25 53 77 0 52 30 96 93 32 89 70 89 55 71 79 40 10 64 80 30 19 62 67 98 42 8 32 57 27 22 1 38 89 52 74 43 8 2 65 82 20 67 22 43 22 95 16 48 25 6 75 86 96 3 85 43 69 93 4 61 53 81 43 84 20 15 34 22 35 26 28 33 67 19 79 19 45 8 13 51 0 86 68 18 47 82 3 16 80 0 18 39 22 5 26 65 70 21 92 66 65 14 6 46 46 21 32 80 35 86 6 67 29 42 71 14 77 55 3 1 14 38 71 82 41 65 12 5 77 3 67 22 59 40 81 48 63 63 25 45 32 78 83 26 96 18 99 45 56 31 30 45 47 80 1 7 81 18 1 90 15 71 22 69 44 18 31 60 16 93 13 17 44 97 98 51 46 42 22 47 72 97 24 52 55 59 25 100 28 5 14 76 32 41 97 61 32 20 0 2 8 41 52 77 35 22 98 78 92 68 29 82 33 28 16 5 9 21 13 26 39 59 69 10 42 4 13 80 34 42 100 44 32 70 15 32 8 83 10 23 73 8 53 7 21 10 52 14 82 28 24 33 94 59 4 17 73 53 85 31 100 74 74 12 72 38 34 14 22 53 0 30 95 3 52 79 41 36 81 25 24 67 48 95 44 7 96 77 90 48 92 45 78 93 95 38 71 4 83 79 64 89 0 76 81 34 66 1 13 58 4 40 5 24 17 6 65 13 13 76 3 20 8 36 12 60 37 42 53 87 10 65 42 25 47 41 33 71 69 94 24 12 92 11 71 3 82 91 90 20 95 44 76 60 34 95 49 40 89 4 45 27 9 34 82 59 2 20 68 22 29 10 1 23 19 47 16 76 47 49 90 94 10 18 55 69 14 26 59 77 73 8 21 72 1 74 76 51 94 44 24 98 71 77 59 9 12 49 38 72 22 55 35 61 16 48 41 21 67 74 92 4 7 85 34 92 39 96 42 26 1 1 4 64 33 96 62 23 67 76 26 47 32 73 82 30 14 61 21 92 40 4 2 38 76 64 8 14 3 49 71 31 38 86 98 17 15 98 32 55 69 46 61 3 44 67 50 44 76 0 45 23 25 11 82 99 11 39 50 40 21 52 17 60 44 90 44 6 16 38 3 41 43 56 26 24 0 9 90 36 50 13 42 88 87 66 32 28 73 94 52 11 35 47 9 87 37 57 15 56 38 95 6 43 23 30 84 39 88 69 5 34 81 93 86 2 77 10 28 30 97 68 14 12 88 1 100 35 73 30 2 43 11 41 58 82 6 84 71 16 18 67 41 100 92 78 57 7 35 69 56 76 13 93 26 26 38 21 96 7 88 2 60 17 54 95 26 2 0 21 87 11 96 36 83 88 31 24 24 62 14 88 84 39 22 17 84 96 1 78 91 53 9 35 75 87 100 33 80 42 7 20 50 65 81 92 14 45 96 34 6 20 86 51 4 19 70 91 13 0 42 70 43 15 47 14 96 72 41 91 11 72 7 92 12 16 51 13 86 40 50 43 55 26 7 1 70 18 71 99 49 55 94 78 40 59 20 96 34 6 28 85 42 70 62 63 32 34 97 80 49 47 50 73 85 63 20 29 0 19 91 84 58 55 33 4 68 55 12 38 49 9 13 99 4 35 26 5 42 29 98 20 95 77 36 63 41 42 45 81 40 53 60 5 55 9 13 34 6 52 28 35 33 29 21 67 57 61 21 41 95 54 50 19 81 75 67 73 77 47 40 83 16 28
.......

output

#1 71
#2 76
.......

Solution & Inpression

제약 사항을 보면 학생수는 1000명이고 학생의 점수는 0~100 사이의 값으로 0점부터 100점까지의 점수를 받은 학생수를 저장할 배열의 크기를 101로 해당 점수를 맞은 학생수를 하나씩 증가시켜 최종적으로 배열에서 가장 큰 값을 출력하였다.

Code

언어 : JAVA

메모리 : 52,420 kb

실행시간 : 202 ms

import java.util.Arrays;
import java.util.Scanner;
import java.io.FileInputStream;

public class Solution{
    public static void main(String args[]) throws Exception {
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();


        for (int i = 1; i <= N; i++) {
            int num = s.nextInt();
            int[] array = new int[1000]; 

            for (int j = 0; j < 1000; j++) { 
                array[j] = s.nextInt();
            }


            int[] countarray = new int[101];

            for (int j = 0; j < 1000; j++) {
                countarray[array[j]]++; 
            }

            int result = 0;
            int temp = 0;

            for (int j = 100; j >= 0; j--) {
                if (result < countarray[j]) {
                    result = countarray[j];
                    temp = j;
                }
            }

            System.out.println("#" + num + " " + temp);

        } 
    }
}

[BOJ] 5427. 불 - BFS

제출일 : 2019-09-04

문제 풀이 시간 : 1H 15M

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/5427

Input

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

Output

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 IMPOSSIBLE을 출력한다.

Example

input

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

output

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

Solution & Inpression

BFS 응용 문제.불이 먼저 퍼지고 사람이 이동. 한턴 한턴 수행하면 쉽게 풀리는 문제였지만 처음부터 생각하기 힘들었던 문제.

Code

언어 : JAVA

메모리 : 119,172 kb

실행시간 : 720 ms

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class pos {
        int y;
        int x;

        pos(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("res/백준_5427_불.txt"));
        int dy[] = { -1, 1, 0, 0 };
        int dx[] = { 0, 0, 1, -1 };
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        Queue<pos> fire = new LinkedList<>();
        Queue<pos> me = new LinkedList<>();
        for (int tc = 1; tc <= T; tc++) {
            me.clear();
            fire.clear();
            boolean flag = false;
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            char[][] map = new char[h][w];
            boolean[][] visit = new boolean[h][w];
            int py = 0, px = 0, flame = 0, per = 0;
            for (int y = 0; y < h; y++) {
                map[y] = br.readLine().toCharArray();
                for (int x = 0; x < w; x++) {
                    if (map[y][x] == '*') {
                        fire.offer(new pos(y, x));
                    } else if (map[y][x] == '@') {
                        visit[y][x] = true;
                        me.offer(new pos(y, x));
                        map[y][x] = '.';
                    }
                }
            }
            int result = 0;
            while (!me.isEmpty()) {
                result++;
                flame = fire.size();
                for (int f = 0; f < flame; f++) {// 불을 먼저 붙여버리겠음
                    int y = fire.peek().y;
                    int x = fire.peek().x;
                    fire.poll();
                    for (int i = 0; i < 4; i++) {
                        int ny = y + dy[i];
                        int nx = x + dx[i];
                        if (ny >= 0 && nx >= 0 && ny < h && nx < w && map[ny][nx] == '.') {
                            map[ny][nx] = '*';
                            fire.offer(new pos(ny, nx));
                        }
                    }
                }

                per = me.size();
                for (int pidx = 0; pidx < per; pidx++) {
                    py = me.peek().y;
                    px = me.peek().x;
                    me.poll();
                    if ((py == 0 || px == 0 || py == h - 1 || px == w - 1)) { // 다음번에 바로간다
                        flag = true;
                        me.clear();
                        break;
                    }
                    for (int i = 0; i < 4; i++) {
                        int npy = py + dy[i];
                        int npx = px + dx[i];
                        if (npy >= 0 && npx >= 0 && npy < h && npx < w && map[npy][npx] == '.' && !visit[npy][npx]) {
                            me.offer(new pos(npy, npx));
                            visit[npy][npx] = true;
                        }
                    }
                }
            }
            if (flag)
                System.out.println(result);
            else
                System.out.println("IMPOSSIBLE");
        }
    }
}

[BOJ] 6593. 상범빌딩 - BFS

제출일 : 2019-09-23

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/6593

Input

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다.

Output

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

Example

input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

output

Escaped in 11 minute(s).
Trapped!

Solution & Inpression

2차원 배열의 BFS문제들과 비슷하게 풀어나갔다. 다만 탐색을 6방향으로 해야 문제를 해결할 수 있다.

Code

언어 : JAVA

메모리 : 18,104kb

실행시간 : 148ms

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

public class Main {
    static int L, R, C;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            L = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            if (L == 0)
                break;

            char[][][] building = new char[L][R][C];
            boolean visit[][][] = new boolean[L][R][C];
            Queue<int[]> q = new LinkedList<int[]>();
            for (int k = 0; k < L; k++) {
                for (int i = 0; i < R; i++) {
                    String str = br.readLine();
                    for (int j = 0; j < C; j++) {
                        char cur = str.charAt(j);
                        building[k][i][j] = cur;
                        if (cur == 'S') {
                            q.offer(new int[] { k, i, j, 0 });
                            visit[k][i][j] = true;
                        }
                    }
                }
                br.readLine();
            } // 입력 끝

            int[] dk = { -1, 1, 0, 0, 0, 0 };
            int[] dx = { 0, 0, -1, 1, 0, 0 };
            int[] dy = { 0, 0, 0, 0, -1, 1 };
            int res = Integer.MAX_VALUE;

            while (!q.isEmpty()) {
                int[] cur = q.poll();
                 //System.out.println(Arrays.toString(cur));
                if (building[cur[0]][cur[1]][cur[2]] == 'E') {
                    res = (cur[3] > res) ? res : cur[3];
                    continue;
                }
                for (int k = 0; k < 6; k++) {
                    int l = cur[0] + dk[k];
                    int x = cur[1] + dx[k];
                    int y = cur[2] + dy[k];
                    if (range(l, x, y) && !visit[l][x][y] && building[l][x][y] != '#') {
                        visit[l][x][y] = true;
                        q.offer(new int[] { l, x, y, (cur[3] + 1) });
                    }
                }
            }
            System.out.println((res == Integer.MAX_VALUE) ? "Trapped!" : "Escaped in " + res + " minute(s).");

        }
    }

    private static boolean range(int l, int x, int y) {
        if (0 <= l && l < L && 0 <= x && x < R && 0 <= y && y < C)
            return true;
        return false;
    }
}

[SWEA] 1263. 사람 네트워크2 D6 - Floyed Warshall

제출일 : 2019-09-23

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN

Input

맨 위의 줄에는 전체 테스트 케이스의 수 T가 주어진다.

그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄에 주어지며, 사람 수인 양의 정수 N이 주어진 다음, 사람 네트워크의 인접 행렬이 행 우선 (row-by-row) 순으로 주어진다.

단, 각 숫자 사이에는 1개의 공백이 주어진다.

Output

총 T줄에 T개의 테스트 케이스 각각에 대한 답을 한 줄에 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 사람 그래프에서 사람들의 CC 값들 중에서 최솟값을 한 줄에 출력한다.

Constraints

입력으로 주어지는 사람 네트워크에서 노드 자신을 연결하는 간선은 없다.

또한 사람 네트워크는 하나의 연결 요소(connected component)로 구성되어 있다.

단, 사람 네트워크의 최대 사용자 수는 1,000 이하이다.

테스트 케이스들은 아래의 그룹들로 이루어져 있다.

그룹 1 싸이클이 없고 N <= 10 인 경우
그룹 2 싸이클이 없고 10 < N <= 100 인경우
그룹 3 싸이클이 있고 N<= 10
그룹 4 싸이클이 있고10 < N <= 100
그룹 5 모든 경우가 존재하고 100 < N <= 1000

Example

input

20
5 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0
5 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0
...

output

#1 4
#2 5
…

Solution & Inpression

플루이드 워샬 알고리즘을 이용하여 해결하였다.

Code

언어 : JAVA

메모리 : 120,644 kb

실행시간 : 3,686 ms

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

public class Solution {

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/D6_1263_사람네트워크2.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            System.out.print("#" + tc + " ");
            int N = sc.nextInt();
            int[][] matrix = new int[N][N];
            int INF = 987654321;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int tmp = sc.nextInt();
                    if (i != j && tmp == 0)
                        matrix[i][j] = INF;
                    else
                        matrix[i][j] = tmp;
                }
            }

            for (int k = 0; k < N; k++) {
                for (int i = 0; i < N; i++) {
                    if (k == i)
                        continue;
                    for (int j = 0; j < N; j++) {
                        if (j == k || i == k)
                            continue;
                        if ((matrix[i][k] + matrix[k][j]) < matrix[i][j])
                            matrix[i][j] = matrix[i][k] + matrix[k][j];
                    }
                }
            }
            int min = INF;
            for (int i = 0; i < N; i++) {
                int sum = 0;
                for (int j = 0; j < N; j++) {
                    sum += matrix[i][j];
                }
                if (sum < min) {
                    min = sum;
                }
            }
            System.out.println(min);
        }
    }
}

[SWEA] 1486. 장훈이의 높은 선반 D4 - PowerSet

제출일 : 2019-08-22

문제 풀이 시간 : 2H 30M

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw

Input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)가 공백으로 구분되어 주어진다.

S는 두 번째 줄에서 주어지는 점원들 키의 합이다.

두 번째 줄에는 N개의 정수가 공백으로 구분되어 주어지며, 각 정수는 각 점원의 키 Hi (1 ≤ Hi ≤ 10,000)을 나타낸다.

Output

각 테스트 케이스마다 첫 번째 줄에는 ‘#t’(t는 테스트 케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 만들 수 있는 높이가 B 이상인 탑 중에서 탑의 높이와 B의 차이가 가장 작은 것을 출력한다.

Example

input

1
5 16
1 3 3 5 6

output

#1 1

Solution & Inpression

DFS로도 해결 할 수 있었지만 PowerSet(멱집합)을 이용하여 해결 하였다.

Code

언어 : JAVA

메모리 : 19,768 kb

실행시간 : 182 ms

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

public class Solution{
    public static int N, B, result;
    public static int[] high;

    public static void sol() {
        int i, j;
        for (i = 0; i < (1 << N); ++i) {
            int sum = 0;
            for (j = N - 1; j >= 0; --j) {
                // System.out.print(((i >> j) & 1));
                if (((i >> j) & 1) == 1)
                    sum += high[j];
            }
            // System.out.println();
            if (sum >= B)
                result = (result > sum) ? sum : result;
        }
    }

    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++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // N, B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)
            N = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());

            high = new int[N];

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

            result = Integer.MAX_VALUE;
            sol();

            System.out.println("#" + tc + " " + (result - B));
        }
        br.close();
    }
}