[BaekJoon] 1062 가르침

🔦 문제 링크

✍️ 풀이

---

• 5개 미만 일 때와 5개 이상일 때를 구분해야한다.
• 무조건 배워야 하는 알파벳은 배웠음을 체크해둔다.
• DFS를 통해 k개 알파벳의 모든 경우의 수를 따져볼 수 있다.

<시간초과 해결>
배우는 순서는 중요하지 않기 때문에 이전에 배운 단어를 다시 볼 필요는 없다.
따라서, 현재 알파벳이후 부터 검사를 시작하도록 한다.

🛠 코드

---

import sys
n, k = map(int, input().split())
arr = [sys.stdin.readline().rstrip()[4:-4] for _ in range(n)]
alpha = [False] * 26
if k < 5:
    print(0)
    exit(0)
else:
    k -= 5
al = ['a', 'n', 't', 'i', 'c']
for a in al:
    alpha[ord(a)-ord('a')] = True
mx = -1


def solve(start, index):
    global mx
    if index==k:
        count = 0
        for ar in arr:
            flag = True
            for a in ar:
                if not alpha[ord(a)-ord('a')]:
                    flag = False
                    break
            if flag:
                count += 1
        mx = max(mx, count)
        return
    else:
        for i in range(start, 26):
            if not alpha[i]:
                alpha[i] = True
                solve(i, index+1)
                alpha[i] = False
        return


solve(0, 0)

print(mx)

📝 정리

---

• 시간초과 를 해결하는 방법 -> 문제가 순서가 중요한지를 확인

🎈 참고

---

dirmathfl 블로그