[BOJ]16500_문자열 판별

문자열 판별

풀이

result 는 문자열의 idx번째 글자부터 마지막 글자까지의 sub string을 주어진 단어를 만들 수 있는지를 나타낸다(만들 수 있으면 1, 없으면 0)

idx 크기가 len(S) 까지 오면 A에 포함된 문자열로 S를 만들 수 있다.

재귀함수 사용

이해 안되는 부분

• else: sol(idx+len(A[i])) 에서
  else 와 연결되는 if가 무엇인지 모르겠다. -> for else 문 이라는 문법이 있었음
  

for ... else

for문과 같은 레벨에 else를 둬서 break없이 빠져나온 경우를 처리하는 방법

예제 1

for x in range(4):
  if x == 2:
    print ('loop out')
    break
else:
  print ('loop end')

loop out 

예제 2

for x in range(4):
  # nop
  pass
else:
  print ('loop end')

loop end

코드

def sol(idx):
    global result
    if idx == len(S): # 정답
        result = 1
        return
    if dp[idx]: # 이미 검사한 경우 
        return
    dp[idx] = 1 # 검사했으니 1로 만들어 줌
    for i in range(len(A)):
        if len(S[idx:]) >= len(A[i]): # S가 A[i] 보다 더 길 때만 비교 가능 
            for j in range(len(A[i])): # A에 포함된 단어 길이 
                if A[i][j] != S[idx+j]: # A[i] 단어와 글자 하나하나 비교
                    break
            else:
                sol(idx+len(A[i]))
    return
    
S = input()
A = []
dp = [0] * 101 # 메모제이션 
for _ in range(int(input())):
    A.append(input())
result = 0
sol(0)
print(result)

참조