Problem

---

문제 설명

1. 문자열을 3개의 부분 문자열로 나눌 때 나올 수 있는 모든 경우의 수를 구하고, 오름차순 정렬한다.
2. DFS로 각 경우의 수와 점수를 계산하고, 최대 점수를 갱신한다.

필요한 알고리즘

• DFS

Submitted Code

---

Python

N = int(input())
S = input()

# 부분 문자열 집합 구하기
P = set()

for idx in range(N):
	for i in range(1, N - 1):
		P.add(S[idx:idx+i])

scores = {p: idx + 1 for idx, p in enumerate(sorted(list(P)))}

# DFS
max_score = 0
stack = [(S, 0, 0)]
while stack:
	text, step, score = stack.pop()
    # 3번째 부분 문자열일 때, 점수 계산 및 최고 점수 갱신
	if step == 2:
		try:
			score += scores[text]
		except KeyError:
			pass
		else:
			max_score = max(max_score, score)
		finally:
			continue
	
    # 1~2번째 문자열일 때, 다음 단계 진행
	for i in range(1, N - 1):
		p = text[:i]
		if not p:
			continue
		stack.append((text[i:], step + 1, score + scores[p]))
		
print(max_score)

Code Review

---

1. 부분 문자열 구하기

Challenge Review

---

이번 DFS 문제도 제출 코드가 깔끔하지 않은 것 같다. 해설 기다립니다.

Reference

• 구름톤 챌린지 언어별 문제 해설 - Python, C++