[자바] 백준 17365 - 별다줄 (java)

목차

문제 : boj17365

 

 

필요 알고리즘

• 동적 계획법(다이나믹 프로그래밍, DP), 트라이(Trie) 
  
  • DP를 기본으로 깔고, DP 진행을 효율적으로 하기 위해 트라이를 사용하면 좋은 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final long MOD = 1000000007L;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        TrieRoot trie = setupTrie();

        String str = br.readLine();
        int len = str.length();

        long[] dp = new long[len+1];
        dp[0] = 1;

        for (int i = 1; i <= len; i++) {

            long base = dp[i-1];
            if (base == 0) continue;

            Node iter = trie.root.peek(str.charAt(i-1));
            int pt = i;

            while (true) {
                if (iter == null) break;

                dp[pt] += base * iter.getCnt();
                dp[pt] %= MOD;

                if (pt == len) break;
                iter = iter.peek(str.charAt(pt++));
            }
        }

        System.out.println(dp[len]);
    }

    private TrieRoot setupTrie() throws Exception {
        TrieRoot trie = new TrieRoot();

        int n = Integer.parseInt(br.readLine());
        while (n-->0) {
            trie.add(br.readLine());
        }

        return trie;
    }
}

class TrieRoot {

    Node root;

    public TrieRoot() {
        root = Node.root();
    }

    public void add(String s) {
        Node iter = root;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            iter = iter.retrieveChild(c);
            iter.increaseCnt();
        }
    }
}

class Node {
    private Node[] child;
    private int cnt;

    private Node() {
        child = new Node['z'-'a'+1];
        cnt = 0;
    }

    public static Node root() {
        return new Node();
    }

    public void increaseCnt() {
        cnt++;
    }

    public int getCnt() {
        return cnt;
    }

    public Node retrieveChild(char c) {
        int idx = c - 'a';

        if (child[idx] == null) {
            child[idx] = new Node();
        }

        return peek(c);
    }

    public Node peek(char c) {
        int idx = c - 'a';

        return child[idx];
    }
}