[백준] 17841 UNIST는 무엇의 약자일까? (C++)

UNIST는 무엇의 약자일까? 문제 풀이

[백준] 17841 UNIST는 무엇의 약자일까?

문제

조건 요약

N개의 단어 W1, W2, …, WN이 주어집니다.

• 각 단어 Wi에서 접두사(앞부분)를 0글자 이상 선택하여 Pi를 만듭니다.
• 이렇게 만든 N개의 접두사 P1, P2, …, PN을 이어 붙여서 정확히 “UNIST”가 되는 경우의 수를 구해야 합니다.
• 결과를 1,000,000,007로 나눈 나머지를 출력합니다.

예를 들어, 예제 2에서는 다음과 같은 4가지 경우가 있습니다:

“UNI” + “” + “” + “S” + “T”
“UN” + “IS” + “T” + “” + “”
“UN” + “IS” + “” + “” + “T”
“UN” + “I” + “” + “S” + “T”

풀이 방식

dp를 활용해서 풀이를 해야한다는 것은 바로 생각했다. 그런데 dp를 어떤 방식으로 갱신해야 하는지를 생각하지 못했다. 일단 이 문제는 top-down 방식으로 풀이해야 했는데 첫번째 단어부터 순회하면서, 다음 함수를 부를때 넘겨주는 인자가 중요했다.

dp(int i, int j)

• i: 주어진 단어의 index
• j: UNIST가 형성된 갯수

for 문에서 현재 단어에서 5 - j 개의 남은 문자열 중에서 맞는 문자열을 길이 순서대로 찾아서 dp를 호출하여 더하는 방식으로 풀이가 가능했다.
이러한 방식을 풀이하기 위해 생각해야 했던 방식은, 현재 단어에서 나올 수 있는 가짓수가 그렇게 많지 않다는 생각을 하는 것이 주요 했던 것 같다. i 번째 문자열에서는 가능한 경우의 수가 아예 이 문자열에서 선택하지 않거나, 남은 UNIST 문자열 중에서 남은 문자열을 구성하는 가지의 수를 더한 것이라는 생각을 하지 못했다.

헤맸던 부분 단어를 구성하기 위해서 2차원 배열을 선언해서 거기서 어떻게 갱신을 해야만 하는지만을 계속 생각하고 있었다. 이전에 풀이했었던 방식은 그냥 for문을 통해서 모두 갱신하는 방식을 주로 사용했어서 그 방식에 갇혀서 생각했다. dp를 풀이할때는 memoization 방식이 여러가지 있다는 것을 명심해야 겠다.

답안

참고자료

백준 UNIST는 무엇의 약자일까? 풀러가기