[SWEA] 3813. 그래도 수명이 절반이 되어서는...

Problem

제출일 : 2019-12-11

문제 풀이 시간 : 1H 45M

난이도 : ★★★★

---

link : https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxo6c6AVkDFAW4#

삼성전자에서 생산하는 플래시 드라이브를 포맷하는 프로그램을 작성하려고 한다.

드라이브를 포맷할 때 특정한 초기 데이터를 항상 드라이브에 저장해 두어야 한다. 이 데이터는 매우 자주 엑세스되는 종류라서 이 데이터가 저장된 블록은 수명이 짧아질 수 있다.

플래시 드라이브는 N개의 블록으로 구성된 것으로 생각하고 각 블록은 1부터 N까지 번호가 붙은 것으로 생각하자.

각 블록마다 지금까지 얼마나 많은 엑세스가 있었는지 알고 있어서 i번째 블록이 얼마나 닳았는지(Wear Level)를 표현하는 값 W를 모든 블록에 대해 가지고 있다고 한다.

Wi의 값은 1 이상 200,000 이하의 자연수 값이고, 값이 클수록 닳은 정도가 많아서 남은 수명이 짧다는 의미이다.

초기 데이터를 아무 곳에나 저장한다면 플래시 드라이브의 수명이 아주 작아질 수 있을 것이다.

“그래도 수명이 절반이 되어서는” 안된다는 정책에 따라서 초기 데이터를 플래시 드라이브의 적절한 위치에 배치하여 드라이브 수명을 최대한 길게 하고 싶다.

초기 데이터는 K개의 덩어리로 구성되어 있고, 이들 중 i번째 덩어리는 Si개의 연속된 블록에 저장되어야 한다.

또, 덩어리들은 입력에 주어진 순서대로 작은 번호의 블록부터 저장되어야 한다.

또, 하나의 덩어리가 저장된 블록에는 다른 덩어리를 저장할 수 없다.

위의 예는 플래시 드라이브 블록들의 Wear Level을 표시한 것이다.

초기 데이터가 3개의 덩어리로 구성되어 있고 각 덩어리의 블록 수가 2, 1, 3이라고 하면 다음과 같이 저장했을 때 최대 Wear Level이 3이 되어 최적이 된다.

입력으로 플래시 메모리의 블록 수 N, 각 블록의 Wear Level 값, 초기 데이터의 덩어리 수와 각덩어리가 차지하는 블록 수를 받아서 위의 조건을 만족하도록 저장할 때

가능한 최대 Wear Level의 최소값을 구하는 프로그램을 작성하라.

Constraints

1. 플래시 드라이브의 블록 수 N은 최대 200,000이다. (1≤N≤200,000)

2. 각 블록의 Wear Level 값은 1 이상 200,000이하의 자연수이다. (1≤Wi≤200,000)

3. 초기 데이터의 덩어리 수 K는 1 이상 N 이하이다. (1≤K≤N)

4. 초기 데이터의 덩어리 당 블록 수의 합은 1 이상 N 이하이다. (1≤S1+S2+…+SK≤N)

input

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

그 다음 줄부터는 각 테스트 케이스가 주어지며 각 테스트 케이스의 첫째 줄에는 N과 K의 값이 순서대로 주어진다.

다음 줄에는 W1, W2, …, WN이 순서대로 주어진다.

그 다음 줄에는 S1, S2, …, SK가 순서대로 주어진다.

Output

각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(TC) “를 출력하고, 초기 데이터가 저장된 블록들의 최대 Wear Level의 가능한 최소값을 출력한다.

Example

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

#1 3
#2 5
#3 3

Solution & Inpression

입력이 가능한 최대 N은 200,000이다. 따라서 모든 경우의 수를 탐색하여 답을 구하는 방법으론 문제해결이 불가능한 문제이다.

일반 문제를 결정문제로 바꾸어 생각하여 문제를 풀어야 한다.

거꾸로 생각하는 것으로

답을 X라고 가정했을때 X가 답인 경우엔 X보다 큰 값은 모두 답이고, X가 답이 아닌 경우는 X보다 작은 값은 모두 답이 될 수 없다.

이런 아이디어를 갖고 문제를 접근한다면 보다 쉽게 문제를 해결할 수 있다. 이분탐색을 이용하여 범위를 계속 좁히며 $O(logN)$번의 탐색으로 최종해를 찾을 수 있다.

답이 가능한 경우와 답이 불가능한 경우는 어떻게 확인을 해야할까???

문제에서 입력으로 K개의 덩어리의 블록 수가 들어오는데 이를 배열S에 저장하고

입력받은 배열W를 순회하며 적합성을 파악한다.

Code

언어 : JAVA

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

public class Solution {
    final static int Max = 200009;
    static int[] W = new int[Max], S = new int[Max];
    static int N, K;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

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

            for (int i = 1; i <= N; i++)
                W[i] = sc.nextInt();
            for (int i = 1; i <= K; i++)
                S[i] = sc.nextInt();

            int s = 1, e = Max, m;
            while (s < e) {
                m = (s + e) / 2;
                if (isAvailable(m))
                    e = m;
                else
                    s = m + 1;
            }
            System.out.println("#" + tc + " " + s);
        } // end of TC
        sc.close();
    }// end of Main

    private static boolean isAvailable(int p) {
        int i, now = 1, cont = 0;
        for (i = 1; i <= N; ++i) {
            if (W[i] <= p)
                cont++;
            else
                cont = 0;
            if (cont == S[now]) {
                cont = 0;
                if (++now > K)
                    break;
            }
        }
        return now > K;
    }

}

[SWEA] 3816. 아나그램

제출일 : 2019-12-11

문제 풀이 시간 : 1H 45M

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxo6c6AVkDFAW4#

아나그램이란 문자열의 문자들을 모두 사용하여 재배열한 것을 의미한다.

“abc”의 아나그램은 “abc”, “acb”, “bac”, “bca”, “cab”, “cba” 총 6개이다.

문자열 S1, S2이 차례대로 주어진다. S2의 부분문자열 중 S1의 아나그램인 것의 개수를 구하는 프로그램을 작성하라.

input

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

각 테스트케이스의 첫 줄에 S1, S2가 사이에 공백을 갖고 띄어져 있다.

S1과 S2는 영문 소문자로만 이루어져 있다. (1 ≤ |S1| ≤ |S2| ≤ 100,000)(|S1|, |S2|는 문자열 S1, S2의 길이)

Output

각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(TC) “를 출력하고, 해당 테스트케이스의 아나그램인 것의 개수를 출력한다.

Example

input

4
aba ababababa
abra abracadabra
anan bananaparanabrazil
ab abba

output

#1 4
#2 2
#3 2
#4 2

Solution & Inpression

아나그램이란 문자열의 문자들을 모두 사용하여 재배열한 것이므로 아나그램이 가능한 경우는 사용되는 알파벳의 조합과 그 숫자가 정확하게 일치될때 아나그램이라고 말한다.

따라서 S2의 부분 문자열이 S1의 아나그램이 되려면 S1이 가진 알파벳의 조합과 사용된 수를 구해 counts 배열에 저장하고 각각 탐색하면서 문제를 해결한 풀이가 code1의 풀이이다.

code1의 풀이는 어렵지 않게 구현이 가능했다.

code2는 S2의 부분 문자열을 탐색할때 순차적으로 탐색을 하기에 맨앞의 알파벳과 맨 뒤의 알파벳만이 변경되며 나머지 알파벳은 그대로 사용되기에 양 끝의 알파벳만 확인하며 아나그램을 찾았다.

Code 1

언어 : JAVA

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

public class Solution {
    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/input.txt"));

        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            char[] s1 = sc.next().toCharArray();
            char[] s2 = sc.next().toCharArray();
            int[] counts = new int[26];

            for (int i = 0; i < s1.length; i++) {
                counts[s1[i] - 'a']++;
            }

            int ans = 0;

            for (int i = 0; i < s2.length - s1.length + 1; i++) {
                int[] tmp = new int[26];
                for (int j = i; j < s1.length + i; j++) {
                    tmp[s2[j] - 'a']++;
                }
                boolean flag = true;
                for (int k = 0; k < 26; k++) {
                    if (tmp[k] != counts[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans++;
            }

            System.out.println("#" + tc + " " + ans);

        } // end of TC

    }// end of main
}

Code 2

언어 : JAVA

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

public class Solution {
    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            String str1 = sc.next();
            String str2 = sc.next();

            int ans = 0;
            int[] counts = new int[26];

            for (int i = 0; i < str1.length(); i++) {
                counts[str1.charAt(i) - 'a']++;
            }

            int zero = 0;
            for (int i = 0; i < 26; i++) {
                if (counts[i] == 0) {
                    zero++;
                }
            }

            int len = str1.length();
            for (int i = 0; i < str2.length(); i++) {
                char a = str2.charAt(i);

                if (counts[a - 'a'] == 0) {
                    zero--;
                }
                counts[a - 'a']--;
                if (counts[a - 'a'] == 0) {
                    zero++;
                }


                if (i >= len) {
                    char b = str2.charAt(i - len);
                    if (counts[b - 'a'] == 0) {
                        zero--;
                    }
                    counts[b - 'a']++;
                    if (counts[b - 'a'] == 0) {
                        zero++;
                    }
                }


                if (zero == 26) {
                    ans++;
                }
            }
            System.out.println("#" + tc + " " + ans);
        }
    }
}

[SWEA] 3819. 최대 부분 배열

제출일 : 2019-12-09

문제 풀이 시간 : 1H 45M

난이도 : ★★★☆

Problem

link : https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxo6c6AVkDFAW4#

길이 $N$ 짜리 배열$A[1…N]$이 주어질 때,

부분 배열의 합 $\sum_{k=i}^j A[k]$의 최댓값을 구하는 프로그램을 작성하라. $(1 ≤ i ≤ j ≤ N)$

input

첫 줄에 테스트케이스의 개수 $T$가 주어진다. $(T ≤ 20)$

각 테스트케이스마다 첫 줄에 $N(N ≤ 200,000)$이 주어지고, 다음 $N$ 줄에 걸쳐 각 줄마다 차례대로 $A[i]$가 주어진다.$(|A[i]| ≤ 1,000)$

Output

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여 T 줄에 걸쳐서 출력한다.

Example

input

2
1
3
5
1
3
-5
3
6

output

#1 3
#2 9

Solution & Inpression

길이 N의 최대값이 200,000이기때문에 모든 경우의 수를 구해 최적해를 구하는 방법으론 풀수 없는 문제로
$$
\sum_{k=i}^j A[k]= \sum_{k=1}^j A[k]-\sum_{k=1}^i A[k]
$$
i부터 j까지의 부분 배열의 합은 1부터 j까지의 부분배열의 합에서 1부터 i까지의 부분배열의 합을 뺀것과 같다.

따라서, 입력을 받으며 누적합(1부터 j까지의 부분배열의 합)을 갖는 배열 sum과 누적합의 최솟값(1부터 i까지의 부분 배열의 합)을 갖는 배열 min을 이용하여 문제를 해결하였다.

Code 1

언어 : JAVA

import java.util.Scanner;

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

        for (int tc = 1; tc <= T; tc++) {
            int N = sc.nextInt();
            int[] input = new int[N + 1];
            int[] sum = new int[N + 1];
            int[] min = new int[N + 1];

            for (int i = 1; i <= N; i++) {
                input[i] = sc.nextInt();
                sum[i] = sum[i - 1] + input[i];
                min[i] = sum[i] > min[i - 1] ? min[i - 1] : sum[i];
            }

            int max = sum[1];
            for (int i = 2; i <= N; i++) {
                if (max < sum[i] - min[i - 1])
                    max = sum[i] - min[i - 1];
            }
            System.out.println("#" + tc + " " + max);
        } // end of TC
        sc.close();
    }// end of main
}

Code 2

언어 : JAVA

import java.util.Scanner;

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++) {
            int N = sc.nextInt();
            int[] A = new int[N];

            A[0] = sc.nextInt();

            int max = A[0];
            for (int i = 1; i < N; i++) {
                int num = sc.nextInt();
                A[i] = num;
                if (A[i - 1] + A[i] > A[i]) {
                    A[i] = A[i - 1] + A[i];
                }
                if (max < A[i]) {
                    max = A[i];
                }
            }

            System.out.println("#" + tc + " " + max);
        }
    }
}

[SWEA] 1240. 단순 2진 암호코드 D3 - Simulation

제출일 : 2019-11-16

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AV15FZuqAL4CFAYD

Input

가장 첫줄은 전체 테스트 케이스의 수이다.

각 테스트 케이스의 첫 줄에 두 자연수가 주어지는데 각각 배열의 세로 크기 N, 배열의 가로크기 M이다 (1≤N<50, 1≤M<100).

그 다음 N개의 줄에는 M개의 배열의 값이 주어진다.

Output

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다.

이때 C는 케이스의 번호이다. 같은 줄에 빈칸을 하나 두고, 입력에 주어진 배열에서 정상적인 암호코드들에 포함된 숫자들의 합을 출력한다.

Example

input

2
16 80
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000011101101100010111011011000101100010001101001001101110110000000000
00000000000000011101101100010111011011000101100010001101001001101110110000000000
00000000000000011101101100010111011011000101100010001101001001101110110000000000
00000000000000011101101100010111011011000101100010001101001001101110110000000000
00000000000000011101101100010111011011000101100010001101001001101110110000000000
00000000000000011101101100010111011011000101100010001101001001101110110000000000
00000000000000011101101100010111011011000101100010001101001001101110110000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
11 70
00000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000
00000001100101000110100011010111101101110010011001001101110110000000000
00000001100101000110100011010111101101110010011001001101110110000000000
00000001100101000110100011010111101101110010011001001101110110000000000
00000001100101000110100011010111101101110010011001001101110110000000000
00000001100101000110100011010111101101110010011001001101110110000000000
00000001100101000110100011010111101101110010011001001101110110000000000
00000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000

output

#1 38 
#2 0 

Solution & Inpression

인덱스 조작문제

입력에서 코드 값을 찾아 8개의 값을 구하기가 까다로운 문제였다.

전부 배열로 입력을 받았지만 문자열로 입력을 받아 비교하면 더 시간이 빠르지 않았을까 하는 생각도 든다.

Code

언어 : JAVA

메모리 : 28,036 kb

실행시간 : 156 ms

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

public class Solution {
    static int N, M;
    static int[][] input;
    static int ans;
    static final int[][] code = { { 0, 0, 0, 1, 1, 0, 1 }// 0
            , { 0, 0, 1, 1, 0, 0, 1 }// 1
            , { 0, 0, 1, 0, 0, 1, 1 }// 2
            , { 0, 1, 1, 1, 1, 0, 1 }// 3
            , { 0, 1, 0, 0, 0, 1, 1 }// 4
            , { 0, 1, 1, 0, 0, 0, 1 }// 5
            , { 0, 1, 0, 1, 1, 1, 1 }// 6
            , { 0, 1, 1, 1, 0, 1, 1 }// 7
            , { 0, 1, 1, 0, 1, 1, 1 }// 8
            , { 0, 0, 0, 1, 0, 1, 1 }// 9
    };
    static int[] res;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            M = sc.nextInt();

            input = new int[8][7];
            boolean flag = false;
            for (int i = 0; i < N; i++) {
                String str = sc.next();
                for (int j = 0; j < M; j++) {
                    if (flag) // 이미 코드를 구한경우
                        break;

                    int tmp = str.charAt(j) - '0';
                    if (tmp == 1) {
                        flag = true;
                        j--;
                        for (int r = 0; r < 8; r++) {
                            for (int c = 0; c < 7; c++) {
                                input[r][c] = str.charAt(j++) - '0';
                            }
                        }
                    }
                }
            }

            getCode();
            System.out.println("#" + tc + " " + calc());

        } // end of TC
        sc.close();
    }// end of main

    private static int calc() {
        int result = (res[0] + res[2] + res[4] + res[6]) * 3 + (res[1] + res[3] + res[5]);
        if ((result + res[7]) % 10 == 0) {
            int sum = 0;
            for (int is : res) {
                sum += is;
            }
            return sum;
        } else
            return 0;
    }

    private static void getCode() {
        res = new int[8];
        Arrays.fill(res, -1);
        for (int k = 0; k < 10; k++) {
            for (int i = 0; i < 8; i++) {
                int flag = 0;
                for (int j = 0; j < 7; j++) {
                    if (input[i][j] == code[k][j])
                        flag++;
                }
                if (flag == 7)
                    res[i] = k;
            }
        }
        for (int i = 0; i < 8; i++) {
            if (res[i] == -1) {
                rotate();
                getCode();
                return;
            }
        }
    }

    private static void rotate() {
        int first = 0;
        for (int i = 0; i < 8; i++) {
            int[] tmp = input[i].clone();
            input[i][0] = first;
            for (int j = 1; j <= 6; j++) {
                input[i][j] = tmp[j - 1];
            }
            first = tmp[6];
        }
    }
}

[SWEA] 1961. 숫자 배열 회전 D2

제출일 : 2019-11-16

문제 풀이 시간 : 15M

난이도 : ★

Problem

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

Constraints

N은 3 이상 7 이하이다.

Input

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에 N이 주어지고,

다음 N 줄에는 N x N 행렬이 주어진다.

Output

출력의 첫 줄은 '#t'로 시작하고,

다음 N줄에 걸쳐서 90도, 180도, 270도 회전한 모양을 출력한다.

입력과는 달리 출력에서는 회전한 모양 사이에만 공백이 존재함에 유의하라.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

Example

input

10
3
1 2 3
4 5 6
7 8 9
6
6 9 4 7 0 5
8 9 9 2 6 5
6 8 5 4 9 8
2 2 7 7 8 4
7 5 1 9 7 9
8 9 3 9 7 6
…

output

#1
741 987 369
852 654 258
963 321 147
#2
872686 679398 558496
952899 979157 069877
317594 487722 724799
997427 894586 495713
778960 562998 998259
694855 507496 686278
…

Solution & Inpression

인덱스 조작문제

행과 열의 계산이 익숙해지면 쉽게 해결 할 수 있는 문제

Code

언어 : JAVA

메모리 : 26,652 kb

실행시간 : 143 ms

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

public class Solution {
    static int N;
    static int[][] matrix;
    static int[][][] res;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            System.out.println("#" + tc);

            N = sc.nextInt();
            matrix = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    matrix[i][j] = sc.nextInt();
                }
            }
            rotate();
            print();
        } // end of TC
    }// end of Main

    private static void print() {
        for (int i = 0; i < N; i++) {
            for (int k = 0; k < 3; k++) {
                for (int j = 0; j < N; j++) {
                    System.out.print(res[k][i][j]);
                }
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    private static void rotate() {
        res = new int[3][N][N];
        for (int k = 0; k < 3; k++) {
            int r = 0, c = 0;
            for (int j = 0; j < N; j++) {
                for (int i = N - 1; i >= 0; i--) {
                    res[k][r][c++] = matrix[i][j];
                    if (c == N) {
                        r++;
                        c = 0;
                    }

                }
            }

            for (int i = 0; i < N; i++) {
                matrix[i] = res[k][i].clone();
            }
        }
    }
}

[SWEA] 4613. 러시아 국기 같은 깃발 D4 - Simulation

제출일 : 2019-11-16

문제 풀이 시간 : 20M

난이도 : ★★☆

Problem

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

input

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

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

다음 N개의 줄에는 M개의 문자로 이루어진 문자열이 주어진다. i번 째 줄의 j번째 문자는 깃발에서 i번째 행 j번째 열인 칸의 색을 의미한다.

‘W’는 흰색, ‘B’는 파란색, ‘R’은 빨간색을 의미한다. ‘W’, ‘B’, ‘R’외의 다른 문자는 입력되지 않는다.

Output

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여 T 줄에 걸쳐서 출력한다.

Example

input

2
4 5
WRWRW
BWRWB
WRWRW
RWBWR
6 14
WWWWWWWWWWWWWW
WWRRWWBBBBBBWW
WRRRWWWBWWWWRB
WWBWBWWWBWRRRR
WBWBBWWWBBWRRW
WWWWWWWWWWWWWW

output

#1 11
#2 44

Solution & Inpression

가장 윗줄(0번)과 가장 아랫줄(N-1번)은 흰색과 빨간색으로 칠해져야 한다.

따라서 0~N-2까지의 수 중에서 2개의 수를 조합을 이용하여 뽑았는데 첫번째 숫자는 W로 칠해져야 하는 행의 숫자고 두번째 숫자는 B로 칠해져야 하는 행의 숫자이다.

이제 분할하여 색을 칠해줘야하는 경우를 세어 최소값을 구하면 된다.

Code

언어 : JAVA

메모리 : 28,928 kb

실행시간 : 175 ms

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

public class Solution {
    static int N, M;
    static char[][] map;
    static int ans;
    static int[] match;
    static boolean[] visit;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            M = sc.nextInt();
            map = new char[N][M];
            for (int i = 0; i < N; i++) {
                String str = sc.next();
                for (int j = 0; j < M; j++) {
                    map[i][j] = str.charAt(j);
                }
            }
            ans = Integer.MAX_VALUE;
            match = new int[2];
            visit = new boolean[N - 1];
            get(0, 0);

            System.out.println("#" + tc + " " + ans);
        }
    }

    private static void get(int start, int depth) {
        if (depth == 2) {
            solve();
            return;
        }
        for (int i = start; i < N - 1; i++) {
            if (!visit[i]) {
                visit[i] = true;
                match[depth] = i;
                get(i, depth + 1);
                visit[i] = false;
            }
        }

    }

    private static void solve() {
        int cnt = 0;
        // W
        for (int i = 0; i <= match[0]; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 'W')
                    cnt++;
            }
        }
        // B
        for (int i = match[0] + 1; i <= match[1]; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 'B')
                    cnt++;
            }
        }
        // R
        for (int i = match[1] + 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 'R')
                    cnt++;
            }
        }

        if (ans > cnt)
            ans = cnt;
    }
}

[SWEA] 4615. 재미있는 오셀로 게임 D3 - Simulation

제출일 : 2019-11-16

문제 풀이 시간 : 45M

난이도 : ★★☆

Problem

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

input

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

각 테스트 케이스의 첫 번째 줄에는 보드의 한 변의 길이 N과 플레이어가 돌을 놓는 횟수 M이 주어진다. N은 4, 6, 8 중 하나이다.

그 다음 M줄에는 돌을 놓을 위치와 돌의 색이 주어진다.

돌의 색이 1이면 흑돌, 2이면 백돌이다.

만약 3 2 1이 입력된다면 (3, 2) 위치에 흑돌을 놓는 것을 의미한다.

돌을 놓을 수 없는 곳은 입력으로 주어지지 않는다.

Output

각 테스트 케이스마다 게임이 끝난 후 보드 위의 흑돌, 백돌의 개수를 출력한다.

흑돌이 30개, 백돌이 34인 경우 30 34를 출력한다.

Example

input

10
5
0 1 1 0 0
0 0 1 0 3
0 1 0 1 0
0 0 0 0 0
1 0 5 0 0
5
0 0 1 1 0
0 0 1 0 2
0 0 0 1 0
0 1 0 0 0
1 0 5 0 0
…

output

#1 9
#2 8
…

Solution & Inpression

시뮬레이션 문제

예전에 한번 풀었던 문제여서 수월하게 풀수 있었다.

요즘 시뮬레이션 문제가 어렵게 느껴져 시뮬레이션 문제를 많이 풀어보려 생각중이다

항상 시뮬레이션 문제를 풀때는 문제를 정확히 읽고 요구사항대로 작성을 하면 되지만 쉬운일이 아니다.....

Code

언어 : JAVA

메모리 : 33,700 kb

실행시간 : 165 ms

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

public class Solution {
    static int N;// 보드 한변의 길이 (4, 6, 8 중 하나)
    static int M;// 플레이어가 돌을 놓는 횟수

    // 상, 하, 좌, 우, 좌상, 우하, 우상, 좌하
    static final int[] dr = { -1, 1, 0, 0, -1, 1, -1, 1 };
    static final int[] dc = { 0, 0, -1, 1, -1, 1, 1, -1 };

    static int[][] map;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            M = sc.nextInt();
            init();
            for (int i = 0; i < M; i++) {
                int r = sc.nextInt() - 1;
                int c = sc.nextInt() - 1;
                int player = sc.nextInt();// 1이면 흑돌 2이면 백돌
                put(r, c, player);
            }
            System.out.println("#" + tc + " " + sum());
        } // end of TC
        sc.close();
    }

    private static String sum() {
        int[] res = new int[2];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1)
                    res[0]++;
                else if (map[i][j] == 2)
                    res[1]++;
            }
        }
        return res[0] + " " + res[1];
    }

    private static void init() {
        map = new int[N][N];
        int half = N / 2;
        map[half - 1][half] = 1;
        map[half][half - 1] = 1;
        map[half - 1][half - 1] = 2;
        map[half][half] = 2;
    }

    private static void put(int r, int c, int player) {
        map[r][c] = player;
        for (int dir = 0; dir < 8; dir++) {
            check(r, c, dir);
        }
    }

    private static void check(int r, int c, int dir) {
        int nr = r + dr[dir];
        int nc = c + dc[dir];

        while (true) {
            if (!isRange(nr, nc) || map[nr][nc] == 0)
                break;

            if (map[r][c] != map[nr][nc]) {
                nr += dr[dir];
                nc += dc[dir];
            } else
                break;
        }

        if (isRange(nr, nc) && map[nr][nc] == map[r][c]) {
            while (r != nr || c != nc) {
                map[nr][nc] = map[r][c];
                nr -= dr[dir];
                nc -= dc[dir];
            }
        }

    }

    private static boolean isRange(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N)
            return true;
        return false;
    }
}

[SWEA] 2383. 점심 식사시간 - Simulation

제출일 : 2019-11-12

문제 풀이 시간 : 2D

난이도 : ★★★★★

Problem

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

Constraints

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초
2. 방의 한 변의 길이 N은 4 이상 10 이하의 정수이다. (4 ≤ N ≤ 10)
3. 사람의 수는 1 이상 10 이하의 정수이다. (1 ≤ 사람의 수 ≤ 10)
4. 계단의 입구는 반드시 2개이며, 서로 위치가 겹치지 않는다.
5. 계단의 길이는 2 이상 10 이하의 정수이다. (2 ≤ 계단의 길이 ≤ 10)
6. 초기에 입력으로 주어지는 사람의 위치와 계단 입구의 위치는 서로 겹치지 않는다.

input

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 방의 한 변의 길이 N이 주어진다.

다음 N줄에는 N*N 크기의 지도의 정보가 주어진다.

지도에서 1은 사람을, 2 이상은 계단의 입구를 나타내며 그 값은 계단의 길이를 의미한다.

Output

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

각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)

Example

input

10
5
0 1 1 0 0
0 0 1 0 3
0 1 0 1 0
0 0 0 0 0
1 0 5 0 0
5
0 0 1 1 0
0 0 1 0 2
0 0 0 1 0
0 1 0 0 0
1 0 5 0 0
…

output

#1 9
#2 8
…

Solution & Inpression

모의 SW 역량테스트문제

1. 지도의 크기가 $N\times N$이고 사람, 계단의 길이가 주어진다.
   • 사람은 1 계단의 길이는 2 이상 10 이하
   • 계단의 개수는 2개이며 사람의 수는 최대 10명이다
2. 각 사람은 두 계단 중 한곳에 도착하여, 계단을 내려간다.
   • 계단을 완전이 내려가는 시간은 계단의 길이 K 만큼의 시간이 소요된다.
   • 계단은 최대 3명까지 동시에 이용이 가능
   • 계단에 도착하면 1분 후에 용이 가능

계단의 개수가 2개로 고정되기때문에 중복순열을 이용하여 각 사람이 이용할 수있는 모든 경우를 구한뒤

해당 경우의 시간을 구해 문제를 해결하였다.

지금까지 풀었던 문제중에 가장 어려웠던 문제였다.

Code

언어 : JAVA

메모리 : 36,012 kb

실행시간 : 177 ms

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

class Point { // 방에서의 위치를 나타내는 클래스
    int r, c;

    public Point(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Solution {
    static int N, M, S;
    static int match[];

    static Point[] man;
    static Point[] stair;
    static int[] length;

    static int answer;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            M = 0; // 사람 수
            S = -1; // 계단 수

            man = new Point[10]; // 최대 사람은 10명(위치 좌표를 저장)
            stair = new Point[2]; // 계단은 2개(위치 좌표를 저장)
            length = new int[2];// 계단의 길이 저장
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    int tmp = sc.nextInt();
                    if (tmp == 1)
                        man[M++] = new Point(i, j);
                    else if (tmp != 0) {
                        stair[++S] = new Point(i, j);
                        length[S] = tmp;
                    }
                }
            }

            answer = Integer.MAX_VALUE;
            match = new int[M];
            dfs(0); // 모든 경우의 수를 구한다.
            System.out.println("#" + tc + " " + answer);
        }
        sc.close();
    }

    // 중복순열: 모든 경우의 수를 구한다 최대 2^10
    private static void dfs(int depth) {
        if (depth == M) {
            solve();
            return;
        }
        for (int i = 0; i < 2; i++) {
            match[depth] = i;
            dfs(depth + 1);
        }
    }

    // 각사람이 어느 계단을 이용할 지 정해졌을 때에 필요한 시간을 계산하는 함수
    private static void solve() {
        PriorityQueue<Integer> pq0 = new PriorityQueue<>();
        PriorityQueue<Integer> pq1 = new PriorityQueue<>();

        for (int i = 0; i < M; i++) {
            if (match[i] == 0)
                pq0.add(dist(man[i], stair[0]));
            else
                pq1.add(dist(man[i], stair[1]));
        }

        int man = M; // 남은 이용자.
        int[] stair0 = new int[3]; // 계단을 이용하는 사람들의 남은 이용시간.
        int[] stair1 = new int[3];

        int time = 0;
        while (true) {

            // 종료 조건 : 계단을 모든 이용자가 이용할 때 까지.
            if (man == 0) {
                boolean flag = true;
                for (int i = 0; i < 3; i++) {
                    if (stair0[i] != 0) {
                        flag = false;
                        break;
                    }
                    if (stair1[i] != 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    break;
            }

            for (int i = 0; i < 3; i++) { // 계단은 최대 3명까지 동시에 이용할 수 있다.
                if (stair0[i] == 0) { // 현재 이용하는 사람이 없을때
                    if (!pq0.isEmpty()) { // 이용할 사람이 있고(큐가 비어있지 않다면)
                        if (pq0.peek() <= time) { // 도착했다면
                            man--; // 남은 이용자수를 내린다.
                            stair0[i] = length[0];// 해당 계단의 이동시간을 주고
                            pq0.poll();
                        }
                    }
                } else { // 현재 계단을 사용하고 있다면
                    stair0[i]--; // 값을 내리고
                    if (stair0[i] == 0) {// 계단을 이용하고 있지 않다면.
                        if (!pq0.isEmpty()) {
                            if (pq0.peek() <= time) {
                                man--; // 이용자를 내린다.
                                stair0[i] = length[0];
                                pq0.poll();
                            }
                        }
                    }
                }

                if (stair1[i] == 0) { // 현재 이용하는 사람이 없을때
                    if (!pq1.isEmpty()) { // 이용할 사람이 있고(큐가 비어있지 않다면)
                        if (pq1.peek() <= time) { // 도착했다면
                            man--; // 남은 이용자수를 내린다.
                            stair1[i] = length[1];// 해당 계단의 이동시간을 주고
                            pq1.poll();
                        }
                    }
                } else { // 현재 계단을 사용하고 있다면
                    stair1[i]--; // 값을 내리고
                    if (stair1[i] == 0) {// 계단을 이용하고 있지 않다면.
                        if (!pq1.isEmpty()) {
                            if (pq1.peek() <= time) {
                                man--; // 이용자를 내린다.
                                stair1[i] = length[1];
                                pq1.poll();
                            }
                        }
                    }
                }

            } // end of for

            time++;
        } // end of while

        if (time < answer)
            answer = time;
    }

    private static int dist(Point man, Point stair) {
        return Math.abs(man.r - stair.r) + Math.abs(man.c - stair.c);
    }

}