백준 2922번 즐거운 단어 Java

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

문제

---

생각하기

---

• 백트래킹, 완전탐색 문제이다.

• 가지치기를 통한 효율 탐색을 한다.

동작

isVisited를 활용해서 문제를 해결하려고 했으나, 조건이 생각보다 까다로워 구현을 못했다.

여러 가지 경우의 수를 생각해 봐야 한다.

조건은

1. 자음이 3번 연속으로 나올 수 없다.
2. L이 무조건 하나는 포함되어야 한다.

따라서, 하나씩 알파벳 하나씩 검사할 때마다 이러한 조건이 부합하는지 판단해야 한다.

결과

코드

---

Java

import java.io.*;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static long ans;
    private static char[] chArr;
    private static final String VOWELS = "AEIOU";

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        DFS(0, 0, 0, false, 1);
        sb.append(ans);
        return sb.toString();
    } // End of solve()

    private static void DFS(int idx, int mo, int ja, boolean l, long count) {
        if (mo >= 3 || ja >= 3) return;

        if (idx == chArr.length) {
            if (l) ans += count;
            return;
        }

        char ch = chArr[idx];
        if (ch == '_') {
            DFS(idx + 1, mo + 1, 0, l, count * 5);
            // 모음 하나 추가

            DFS(idx + 1, 0, ja + 1, l, count * 20);
            // L을 포함하지 않은 자음 20개, 자음 추가, L을 포함해서 21를 할 경우,
            // L이 전체에 포함되지 않는 경우를 고려하지 못함.

            DFS(idx + 1, 0, ja + 1, true, count); // L인 자음을 추가
        } else {
            if (VOWELS.contains(Character.toString(ch))) {
                DFS(idx + 1, mo + 1, 0, l, count);
            } else {
                if (ch == 'L') DFS(idx + 1, 0, ja + 1, true, count);
                else DFS(idx + 1, 0, ja + 1, l, count);
            }
        }
    } // End of DFS()

    private static void input() throws IOException {
        chArr = br.readLine().toCharArray();
        ans = 0;
    } // End of input()
} // End of Main class

Kotlin

import java.io.*

// input
private var br = System.`in`.bufferedReader()

// variables
private lateinit var chArr: CharArray
private var ans = 0L

private val vowels = arrayOf('A', 'E', 'I', 'O', 'U')
private const val L = 'L'

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    DFS(0, 0, 0, false, 1)
    sb.append(ans)
    return sb.toString()
} // End of solve()

private fun DFS(idx: Int, mo: Int, ja: Int, l: Boolean, count: Long) {
    if (mo >= 3 || ja >= 3) return
    if (idx == chArr.size) {
        if (l) ans += count
        return
    }

    val ch = chArr[idx]
    if (ch == '_') {
        DFS(idx + 1, mo + 1, 0, l, count * 5)
        DFS(idx + 1, 0, ja + 1, l, count * 20)
        DFS(idx + 1, 0, ja + 1, true, count)
    } else {
        if (vowels.contains(ch)) {
            DFS(idx + 1, mo + 1, 0, l, count)
        } else {
            if (ch == 'L') DFS(idx + 1, 0, ja + 1, true, count)
            else DFS(idx + 1, 0, ja + 1, l, count)
        }
    }
} // End of DFS()

private fun input() {
    chArr = br.readLine().toCharArray()
} // End of input()