문자열이 입력됩니다. 모든 부분 문자열이 팰린드롬이 되도록 분할하는 방법의 수를 출력하세요.
📥 테스트 입력값
aab
🔎 실행 결과
2
💡 힌트 코치
is_palindrome 확인 후 재귀로 분할 경로를 탐색하세요.
✅ 정답 공개
s = input().strip()
count = [0]
def is_pal(t):
return t == t[::-1]
def dfs(start):
if start == len(s):
count[0] += 1
return
for end in range(start+1, len(s)+1):
if is_pal(s[start:end]):
dfs(end)
dfs(0)
print(count[0])