[SWEA] 4301. 콩 많이 심기 D4 - Simulation

제출일 : 2019-09-24

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWLv-yZah48DFAVV

Input

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

각 테스트 케이스는 한 줄로 이루어져 있으며, 가로길이 N, 세로길이 M이 주어진다.

(1 ≤ N, M ≤ 1000)

Output

각 테스트 케이스마다 밭에 놓을 수 있는 콩의 최대 개수를 출력하라.

Example

input

1
3 2

output

#1 4    

Solution & Inpression

해당 위치에서 콩을 심을 수 있는지 검사한뒤 콩을 심을 수 있다면 콩을 콩을 심는다.

Code

언어 : JAVA

메모리 : 94,668 kb

실행시간 : 279 ms

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

public class Solution {
    static int N, M, cnt;
    static int[][] map;

    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, 세로길이 M (1 ≤ N, M ≤ 1000)
            N = sc.nextInt();
            M = sc.nextInt();

            map = new int[M][N];
            cnt = 0;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    solve(i, j);
                }
            }
            System.out.println("#"+tc+" "+cnt);
        }
        sc.close(); // Scanner close
    }

    private static void solve(int i, int j) {

        int[] dx = { -2, 2, 0, 0 };
        int[] dy = { 0, 0, -2, 2 };

        boolean flag = true;

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

            if (range(nx, ny)) { // 범위 안이고
                if (map[nx][ny] == 1) { // 콩이 심어져 있으면
                    flag = false; // 콩 못심어
                    break;
                }
            }
        }

        if (flag) {
            // System.out.println("i = "+i+", j= "+j);

            map[i][j] = 1;//콩심고
            cnt++; //카운트
        }

    }

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

[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;
    }
}

[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);

        } 
    }
}

[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();
    }
}