아직 맞추지 못한 그리디 문제 1062번 가르침

나는 아직 그리디에 약하다. 이 문제의 경우 시간 초과를 1시간 동안 받다가 포기했다. 오답노트를 해야한다고 생각해서 작성한다.

필수 핵심 아이디어는 문자를 ord 를 통한 수로 만들고, 그것을 index 로 접근하는 것이 주  방법인거 같은데

정확한 파악이 안된다. 이전 내 풀이는 왜 시간 초과지??

 

import collections
import sys

sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline
print = sys.stdout.write


def iinput(): return int(input())


def lisinput(): return list(map(int, input().split()))


def dq(a):
    return collections.deque(a)


def minput(): return map(int, input().split())


def liinput(): return list(map(int, list(input().replace("\n", ""))))


def addNode(a, b):
    return [a[0] + b[0], a[1] + b[1]]


def returnValue(graph, node):
    return graph[node[0]][node[1]]


def transpose(graph):
    return list(map(list, zip(*graph)))


if __name__ == '__main__':
    """
    알파벳 문제는 반드시 ord
    """


    def dfs(idx, cnt):
        global answer
        if cnt == k - 5:
            read_cnt = 0
            for word in words:
                for w in word:
                    if not learn[ord(w) - ord('a')]:
                        break
                    else:
                        read_cnt += 1
            answer = max(answer, read_cnt) if answer else read_cnt
            return

        for i in range(idx, 26):
            if not learn[i]:
                learn[i] = True
                dfs(i, cnt + 1)
                learn[i] = False


    answer = None
    n, k = minput()
    if k < 5 or k == 6:
        print(0 if k < 5 else n)

    else:
        words = [set(input().rstrop()) for _ in range(n)]
        learn = [False for k in range(26)]
        for c in ('a', 'c', 'i', 'n', 't'):
            learn[ord(c) - ord('a')] = True
    dfs(0, 0)
    print(answer)