πŸ“– [λ°±μ€€μ•Œκ³ λ¦¬μ¦˜ 풀이] Q.1759 μ•”ν˜Έ λ§Œλ“€κΈ° 문제 풀이

πŸ“– 문제

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

λ°”λ‘œ μ–΄μ œ μ΅œλ°±μ€€ 쑰ꡐ가 λ°© μ—΄μ‡ λ₯Ό μ£Όλ¨Έλ‹ˆμ— 넣은 채 κΉœλΉ‘ν•˜κ³  μ„œμšΈλ‘œ κ°€ λ²„λ¦¬λŠ” ν™©λ‹Ήν•œ 상황에 μ§λ©΄ν•œ 쑰ꡐ듀은,

702ν˜Έμ— μƒˆλ‘œμš΄ λ³΄μ•ˆ μ‹œμŠ€ν…œμ„ μ„€μΉ˜ν•˜κΈ°λ‘œ ν•˜μ˜€λ‹€. 이 λ³΄μ•ˆ μ‹œμŠ€ν…œμ€ μ—΄μ‡ κ°€ μ•„λ‹Œ μ•”ν˜Έλ‘œ λ™μž‘ν•˜κ²Œ λ˜μ–΄ μžˆλŠ” μ‹œμŠ€ν…œμ΄λ‹€.

μ•”ν˜ΈλŠ” μ„œλ‘œ λ‹€λ₯Έ L개의 μ•ŒνŒŒλ²³ μ†Œλ¬Έμžλ“€λ‘œ κ΅¬μ„±λ˜λ©° μ΅œμ†Œ ν•œ 개의 λͺ¨μŒ(a, e, i, o, u)κ³Ό μ΅œμ†Œ 두 개의 자음으둜 κ΅¬μ„±λ˜μ–΄ μžˆλ‹€κ³ 

μ•Œλ €μ Έ μžˆλ‹€. λ˜ν•œ μ •λ ¬λœ λ¬Έμžμ—΄μ„ μ„ ν˜Έν•˜λŠ” μ‘°κ΅λ“€μ˜ μ„±ν–₯으둜 미루어 보아 μ•”ν˜Έλ₯Ό μ΄λ£¨λŠ” μ•ŒνŒŒλ²³μ΄ μ•”ν˜Έμ—μ„œ μ¦κ°€ν•˜λŠ” μˆœμ„œλ‘œ

λ°°μ—΄λ˜μ—ˆμ„ 것이라고 μΆ”μΈ‘λœλ‹€. 즉, abcλŠ” κ°€λŠ₯성이 μžˆλŠ” μ•”ν˜Έμ΄μ§€λ§Œ bacλŠ” 그렇지 μ•Šλ‹€.

μƒˆ λ³΄μ•ˆ μ‹œμŠ€ν…œμ—μ„œ 쑰ꡐ듀이 μ•”ν˜Έλ‘œ μ‚¬μš©ν–ˆμ„ λ²•ν•œ 문자의 μ’…λ₯˜λŠ” C가지가 μžˆλ‹€κ³  ν•œλ‹€. 이 μ•ŒνŒŒλ²³μ„ μž…μˆ˜ν•œ 민식, μ˜μ‹ ν˜•μ œλŠ”

μ‘°κ΅λ“€μ˜ 방에 μΉ¨νˆ¬ν•˜κΈ° μœ„ν•΄ μ•”ν˜Έλ₯Ό μΆ”μΈ‘ν•΄ 보렀고 ν•œλ‹€. C개의 λ¬Έμžλ“€μ΄ λͺ¨λ‘ μ£Όμ–΄μ‘Œμ„ λ•Œ, κ°€λŠ₯μ„± μžˆλŠ” μ•”ν˜Έλ“€μ„

λͺ¨λ‘ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

πŸ” 접근법

Q.1759 μ•”ν˜Έ λ§Œλ“€κΈ° 문제 ν’€μ΄μž…λ‹ˆλ‹€.

μ•”ν˜Έλ₯Ό λ§Œλ“€κΈ° μœ„ν•΄ λͺ¨λ“  경우λ₯Ό μ™„μ „ 탐색을 ν•΄μ•Ό ν•©λ‹ˆλ‹€.

μ—¬κΈ°μ„œ 문제λ₯Ό 보며 νŒŒμ•…ν•΄μ•Ό ν•  μ€‘μš”ν•œ 것은

λ°”λ‘œ μ•”ν˜Έκ°€ μ¦κ°€ν•˜λŠ” μˆœμ„œλ‘œ λ°°μ—΄λ˜μ–΄μ•Ό ν•œλ‹€λŠ” κ²ƒμž…λ‹ˆλ‹€.

μ΄λŠ” 즉, λ°˜λ“œμ‹œ μ¦κ°€ν•˜λŠ” μˆœμ„œλ‘œ μ˜€λ¦„μ°¨μˆœμœΌλ‘œ 배열이 κ³ μ •λœλ‹€λŠ” 것 μž…λ‹ˆλ‹€.

μˆœμ„œλŠ” 무쑰건 μ˜€λ¦„μ°¨μˆœμœΌλ‘œ 고정이 λ˜μ–΄μ•Ό ν•˜λ―€λ‘œ

쑰합을 톡해 문제λ₯Ό ν•΄κ²°ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

쑰합을 μ΄μš©ν•΄ c개의 문자 쀑 L개의 μ•ŒνŒŒλ²³μ„ κ³ λ₯΄λŠ” κ²½μš°λ“€μ„ 찾으면 λ©λ‹ˆλ‹€.

μ΄λ ‡κ²Œ 쑰합을 톡해 λͺ¨λ“  경우의 μ•”ν˜Έλ₯Ό λ§Œλ“€κ³ 

λ¬Έμ œμ— 주어진 쑰건에 맞게

ν•œ 개 μ΄μƒμ˜ λͺ¨μŒκ³Ό 두 개 μ΄μƒμ˜ 자음이 μžˆλŠ”μ§€λ₯Ό ν™•μΈν•˜μ—¬

쑰건에 λ§žλŠ” μ•”ν˜Έλ§Œ 좜λ ₯ν•΄μ£Όλ©΄ λ©λ‹ˆλ‹€.

πŸ’» μ½”λ“œ

package problem.brute;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main_1759 {
    static int L, C;
    static String[] alphabet;
    static char[] vowels = {'a','e','i','o','u'};
    public static void main(String[] args) throws IOException {
        input();
        Arrays.sort(alphabet);
        solve();
    }



    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String [] input = br.readLine().split(" ");
        L = Integer.parseInt(input[0]);
        C = Integer.parseInt(input[1]);
        alphabet = br.readLine().split(" ");
    }

    public static void solve() {
        boolean[] visited = new boolean[C];
        combination(alphabet, visited, 0, C,L);

    }

    static void combination(String[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            checkWord(arr, visited, n);
            return;
        }

        if (depth == n) {
            return;
        }

        visited[depth] = true;
        combination(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        combination(arr, visited, depth + 1, n, r);
    }

    static void checkWord(String[] arr, boolean[] visited,int n){
        int vowelCount = 0;
        int consonantCount = 0;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            if(visited[i]){
                sb.append(arr[i]);
                char currentChar = arr[i].charAt(0);
                if( isVowel(currentChar) ){
                    vowelCount++;
                }else{
                    consonantCount++;
                }
            }
        }
        if(vowelCount >= 1 && consonantCount >= 2){
            System.out.println(sb.toString());
        }
    }

    static boolean isVowel(char c){
        for(int i=0; i<vowels.length; i++){
            if(vowels[i] == c){
                return true;
            }
        }
        return false;
    }
}

Written on February 13, 2021