백트래킹

풀이 백트래킹 문제이다. 먼저 입력값으로 주어지는 배열의 크기 N과 부분수열의 합 S를 입력는다. 배열 arr[20]에 N개의 원소를 입력받는다. 재귀 함수 dfs를 구현합니다. 이 함수는 현재 인덱스(idx)와 현재까지의 합(sum)을 인자로 받는다. 재귀 함수 dfs의 동작은 다음과 같다: 현재 인덱스의 원소를 합에 더해줍니다: sum += arr[idx]; 만약 합이 S와 같다면, 카운트를 증가시킵니다: if (sum == S) { cnt++; } 현재 인덱스의 다음 원소부터 탐색하기 위해 for문을 사용하여 재귀 호출합니다: for (int i = idx + 1; i < N; i++) { dfs(i, sum); } 모든 원소에 대해 dfs를 호출하여 부분수열의 합이 S와 같은 경우의 수를 구한다...

N과 M 2번 풀이를 참고해 완성할 수 있었습니다. 푸는 순서 1. 입력을 사전순으로 정렬합니다. 2. 백트래킹을 이용해 조합을 구현합니다. 3. 모음, 자음 수를 체크해 조건을 충족하는 경우에만 출력합니다. L, C = map(int, input().split()) characters = list(input().split()) characters.sort() password = [] visited = [0] * C def backtrack(depth, start): if depth == L: consonant = 0 vowel = 0 for word in password: if word == "a" or word == "e" or word == "i" or word == "o" or word == "u..

www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 알파벳 대문자로 이루어진 단어에서 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제. 0 ~ 9까지의 숫자는 10개이므로 백트래킹을 통해 풀 수 있습니다. 각 알파벳에 대응되는 숫자의 조합들을 백트래킹을 통해 구하고 각 알파벳을 숫자로 치환 후 계산하여 답을 구하면 됩니다. #include #include #include using namespace std; #define..