[BOJ] 1062번 : 가르침(Go, Golang)

문제 링크 : 백준 1062번

[문제 접근]

알파벳 개수가 작기 때문에 전부 탐색할 수 있을 것 같아서 사용할 수 있는 알파벳의 조합으로 풀었다.

1. 먼저 k가 5보다 작으면 무조건 0이고 26이면 무조건 n개 이다.
2. visit배열에 a,c,i,n,t를 true로 변경시키고(아스키 코드를 이용) k에서 5를 빼준다.
3. sel 함수로 들어가 a,c,i,n,t를 제외한 알파벳 전부를 돌면서 조합으로 k개를 뽑아 test 함수로 들어간다.
4. test 함수에서 n개의 문자열과 비교해 만들 수 있으면 cnt를 증가시킨다.
5. 최종 결과를 ans과 비교하여 더 큰 숫자가 있으면 변경시켜 최대값을 갱신해준다.

[소스 코드]

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	r     = bufio.NewReader(os.Stdin)
	w     = bufio.NewWriter(os.Stdout)
	n, k  int
	s     []string
	visit [30]bool
	ans   = 0
)

func test() int {
	cnt := 0
	for i := 0; i < n; i++ {
		check := true
		for j := 0; j < len(s[i]); j++ {
			if !visit[s[i][j]-'a'] {
				check = false
				break
			}
		}
		if check {
			cnt++
		}
	}

	return cnt
}

func sel(alpha int, cnt int) {
	if cnt == k {
		num := test()
		if ans < num {
			ans = num
		}
		return
	}
	for i := alpha; i < 26; i++ {
		if visit[i] == false {
			visit[i] = true
			sel(i, cnt+1)
			visit[i] = false
		}
	}
}

func main() {
	defer w.Flush()

	fmt.Fscan(r, &n, &k)
	if k < 5 {
		fmt.Fprintln(w, 0)
		return
	} else if k == 26 {
		fmt.Fprintln(w, n)
		return
	}
	s = make([]string, n)
	visit['a'-'a'] = true
	visit['c'-'a'] = true
	visit['i'-'a'] = true
	visit['n'-'a'] = true
	visit['t'-'a'] = true
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &s[i])
		s[i] = s[i][4 : len(s[i])-4]
	}

	k -= 5
	sel(0, 0)
	fmt.Fprintln(w, ans)

}