[백준][C] 1062-가르침/Brute Force/브루트 포스/비트 마스킹/조합/재귀/백트래킹/DFS

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

1062번: 가르침

 

 

🗺 시도

브루트포스와 관련된 문제를 연습하기위해 1062번 문제를 풀어보았다.

• abc를 알던, bca를 알던 읽을 수 있는 단어는 같기 때문에 조합을 사용해야겠다는 생각이 들었다.

  • //조합 Combination
    #include <stdio.h>
    
    int n = 4, r = 3; //4개 중에서 3개 뽑기 (순서상관없이)
    int check[4];
    int result[3]; //결과를 담을 배열
    int arr[] = { 1,2,3,4 };
    
    void combination(int idx, int count) { //조합
    	if (count == r) {
    		for (int i = 0; i < r; i++) {
    			printf("%d", result[i]);
    		}
    		printf("\n");
    		return;
    	}
    
    	for (int i = idx; i < n; i++) {
    		if (check[i] != 1) {
    			result[count] = arr[i];
    			check[i] = 1; // TRUE
    			combination(i, count + 1);
    			check[i] = 0; //FALSE
    		}
    	}
    }
    int main(void) {
    	combination(0, 0);
    }

• 무조건 a, n, t, i, c는 배워야하기 때문에! k가 5보다 큰 경우에서만 함수를 수행하게 만들었다.
• 배운 알파벳은 isLearned배열에 배웠다고 표시해준다.
• k-5개 만큼 다 배웠다면, 아까 입력받아놓았던 문자열 글자들의 isLearned가 TRUE인지 체크한다.
  • 입력받은 단어가 배운 단어 중에 하나라도 없다면 배울 수 없는 단어로 취급하고
  • isLearned된 글자로 단어를 읽을 수 있다면 result를 증가시킨다.
• 만들 수 있는 모든 알파벳의 조합을 가지고 바로 위의 단계를 반복한다.

 

🏔 코드 구현

 

📜느낀점 

• 비주얼 스튜디오 2019에서는 내장함수인 max를 사용할 수 있었는데, 백준에서는 max함수가 선언되지 않은 함수라고 컴파일 에러라고 했다. 왜 그런지 이유를 알아봐야겠다.
• 처음에는 문제를 이해못해서 어려웠는데, 문제만 이해가 된다면 어렵지 않은 문제였다.
• 비트마스킹을 이용해서도 풀 수 있는 것 같은데, 비트 연산을 공부한 다음에 꼭 다시 비트마스킹으로 풀어봐야겠다.