[BOJ] 1062. 가르침

https://www.acmicpc.net/problem/1062

1062번: 가르침

 

 

1. 해결방법

완전탐색 문제이다. 본인은 알파벳을 for문 돌려서 백트래킹을 진행하였다.

처음에는 문제 이해를 잘못해서 몇시간동안 헤맸다...

알파벳 체크 여부인 chk를 만들고, 모든 알파벳을 for문 돌려서 재귀를 호출하는 것이다.
주어진 문자열 하나하나를 따로 보는 것이 아니라, 가르치는 알파벳은 주어진 문자열 모두 공통적으로 적용되는 것이기에 max() 메서드를 사용해서 얼마나 문자열을 알 수 있냐에 대한 카운트를 했다.

 

 

2. 정답코드

import sys
input = sys.stdin.readline

# input
N, K = map(int, input().split())

strings = []
for i in range(N):
    strings.append(list(set(str(input().rstrip()))))


# dfs
def dfs(idx, cnt):
    global answer

    if cnt == (K - 5):
        result = 0
        for string in strings:
            for s in string:
                if chk[ord(s) - ord('a')] == False:
                    break
            else:
                result += 1
        answer = max(answer, result)
        return

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


# main
chk = [False] * 26
alpha_list = ['a', 'c', 'i', 'n', 't']
for alpha in alpha_list:
    chk[ord(alpha) - ord('a')] = True

answer = 0
dfs(0, 0)

print(answer)