[Python] 백준 16500 : 문자열 판별 (dp)

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

머리말

완전 탐색인 줄 알고 왜 시간 초과가 나지 쩔쩔 맺던.. (테스트케이스 완전 불친절하다 😇)

이 문제는 dp 문제이다. 가만 생각해보면 중복 연산이 많으니 메모이제이션을 당연히 해야 한다.

처음 참고한 블로그도 좋은 풀이법이지만, 다른 분(cozyyg)의 풀이가 더 직관적이어서 그 풀이로 다시 공부하였다.

 

접근 방법

 

• dp 배열에는 해당 인덱스까지 A에 포함된 문자열로 표현할 수 있는지 여부를 0, 1로 저장한다.
• 초기값 dp[0]은 1(True)로 두고, 우리의 목표는 dp[len(s)]값이 무엇인지 찾는 것이다.
• 계산 편의를 위해 +1 위치에 결괏값을 저장한다.

추가 테스트 케이스 1

[input]

aaaaaaaaaa
2
aaaa
aaa

[output]

1

추가 테스트 케이스 2

[input]

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
aa
aaaa
aaaaaa
aaaaaaaaaa
aaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

[output]

0

코드

s = input()
n = int(input())
a = [input() for i in range(n)]
dp = [False for _ in range(len(s) + 1)]

dp[0] = True
for i in range(len(s)):
    if not dp[i]:
        continue

    for t in a:
        if s[i:i+len(t)] == t:
            dp[i+len(t)] = True
print(int(dp[len(s)]))

다른 풀이

s = input()
n = int(input())
a = []
for i in range(n):
    a.append(input())
dp = [-1] * (len(s) + 1)

def word(pos):
    if dp[pos] != -1: return dp[pos]

    if pos == len(s): return 1

    dp[pos] = 0
    for i in range(n):
        if s[pos:].startswith(a[i]):
            dp[pos] = max(dp[pos], word(pos + len(a[i])))
    return dp[pos]

print(word(0))

더 읽을거리

• https://kunkunwoo.tistory.com/137