조합 12

[BOJ] 1941. 소문난 칠공주

여러가지 기법이 혼합되어 있는 문제이다. 우선 전체 25개의 알파벳중 7개를 뽑는 경우의 수를 생각하였다. 백트래킹을 이용한 조합을 사용할 계획으로 7개의 알파벳을 고르는 것을 구현한 후 1차적으로 S가 4개 이상인지를 확인하였다. 그 다음 S가 4개이상임이 확인이 된다면 BFS를 이용하여 7개의 알파벳이 하나의 그룹으로 이루어져있는지 확인하였다. 만일 하나의 그룹이면 최종답을 하나추가 시켰다. 수의 범위가 구현이 가능한 범위임으로 문제에 주어진 대로 구현하는게 중요한 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 4..

Algorithm 2020.04.02

[SWEA] 4012. 요리사

조합을 사용하는 문제이다. 백트래킹을 사용하는 comb함수를 구현하여 N개중에서 N/2개를 뽑는 조합의 경우를 구하고, 그 경우 마다 check함수를 적용시켜 서로 다른 두 집합의 시너지 합이 최소가 되는 경우를 찾았다. check함수에서는 visit배열을 기준으로 방문의 유무를 이용하여 두개의 그룹으로 나누었다. 그리고 이 check함수에서도 2개씩 뽑아내야 하는 조합이 있는데 이것은 단순 이중for문으로 구현하였다. 문제를 이해하는데 꽤 많은 시간이 걸려서 다른 블로그를 참고하였다. 문제의 의도를 파악하는 연습이 필요한 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ..

Algorithm 2020.03.24