[BOJ] 1062 - 가르침 (🥇 골드 5티어)

사용 언어: Python3

문제

가르침

풀이

나의 풀이

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
words = [input()[4:-4] for _ in range(N)]

if K < 5: # k 가 5보다 작으면 어떤 언어도 배울 수 없음
    print(0)
elif K == 26: # k 가 26이면 모든 언어를 배울 수 있음
    print(N)
else:
    need_learn = [0] * 26 # 익혀야 하는 알파벳 개수
    visited = [0] * 26 # 익힌 알파벳 체크 (antic 제외)
    already_known = 'antic' # anta, tica

    for word in words:
        for val in word:
            if val in already_known:
                continue
            need_learn[ord(val) - ord('a')] += 1 # 필요한 알파벳의 수 체크

    # 읽을 수 있는 문자들이 learned 일 때, words 중 읽을 수 있는 단어의 수 반환
    def countReadableWords(learned):
        cnt = 0
        for word in words:
            if all(val in learned for val in word): # if word in learned # 이거 아님 !!
                cnt += 1
        return cnt

    # 무조건 a, c, i, n, t 는 배웠다고 가정하고 나머지 배울 알파벳을 k-5까지 dfs로 탐색
    def DFS(L):
        global ans
        if L == K - 5:
            ans = max(ans, countReadableWords(already_known + ''.join(res)))
        else:
            for i in range(26):
                if chr(i + ord('a')) in already_known:
                    continue
                if need_learn[i] == 0 or visited[i]:
                    continue
                res[L] = chr(i + ord('a'))
                visited[i] = 1
                DFS(L+1)
                res[L] = ''
                visited[i] = 0

    res = [''] * (K - 5) # 나머지 배울 알파벳
    ans = -1e9
    DFS(0)
    print(ans)

• 테스트 케이스: 통과
• 제출 결과
  

나의 풀이

from itertools import combinations 
import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
words = [input()[4:-4] for _ in range(N)]

if K < 5: # k 가 5보다 작으면 어떤 언어도 배울 수 없음
    print(0)
elif K == 26: # k 가 26이면 모든 언어를 배울 수 있음
    print(N)
else:
    need_learn = [0] * 123 # 익혀야 하는 알파벳 (z는 122이기 때문)
    learned = [0] * 123 # 익힌 알파벳 체크 (antic 포함)
    already_known = 'antic' # anta, tica

    for x in already_known:
        learned[ord(x)] = 1

    for word in words:
        for val in word:
            if val in already_known:
                continue
            need_learn[ord(val)] = 1 # 익혀야하는 알파벳 체크

    # 읽을 수 있는 단어 수 반환 (learned 읽을 수 있는 문자 라스트)
    def countReadableWords(learned):
        cnt = 0
        for word in words:
            canRead = 1
            for val in word:
                if not learned[ord(val)]: # 배우지 않아서 못 읽는다
                    canRead = 0
                    break
            if canRead:
                cnt += 1
        return cnt
    
    # res는 익혀야하는 알파벳
    res = [chr(i) for i in range(ord('a'), ord('z') + 1) if need_learn[i] == 1]
    ans = -1e9
    for learn in combinations(res, K - 5):
        for l in learn: learned[ord(l)] = 1
        ans = max(ans, countReadableWords(learned))
        for l in learn: learned[ord(l)] = 0 # 백트래킹
    print(ans)

• 테스트 케이스: 통과
• 제출 결과
  

다른 풀이

from itertools import combinations 
import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
words = [input()[4:-4] for _ in range(N)]

if K < 5: # k 가 5보다 작으면 어떤 언어도 배울 수 없음
    print(0)
elif K == 26: # k 가 26이면 모든 언어를 배울 수 있음
    print(N)
else:
    learned = [0] * 123 # ✅ 익힌 알파벳 체크
    first_word = {'a','n','t','i','c'}
    remain_alphabet = set(chr(i) for i in range(ord('a'), ord('z') + 1)) - first_word # ✅ 남은 알파벳

    for x in first_word:
        learned[ord(x)] = 1

    # ✅ 읽을 수 있는 단어 수 반환 (learned 읽을 수 있는 문자 라스트)
    def countReadableWords(learned):
        cnt = 0
        for word in words:
            canRead = 1
            for val in word:
                if not learned[ord(val)]: # 배우지 않아서 못 읽는다
                    canRead = 0
                    break
            if canRead:
                cnt += 1
        return cnt
    
    ans = -1e9
    for learn in combinations(remain_alphabet, K - 5): # ✅ remain_alphabet 에서 (K-5)개 뽑기
        for l in learn:
            learned[ord(l)] = 1
        ans = max(ans, countReadableWords(learned))
        for l in learn:
            learned[ord(l)] = 0 # ✅ 백트래킹
    print(ans)

• 테스트 케이스: 통과
• 제출 결과
  
• 나는 need_learn 이라는 리스트를 만든 뒤, combinations(need_learn, K - 5)으로 진행했는데 그렇게 하면 안됐다.
  combinations(remain_alphabet, K - 5)으로 해야한다.
  • need_learn -> 각 단어에 포함된 알파벳을 체크한다. (anta, tica 제외)
  • remain_alphabet -> first_word를 제외하고 남은 알파벳이다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기