N과 M (6)문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열고른 수열은 오름차순이어야 한다.입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력 1 복사3 14 5 2예제 출력 1 복사245예제 입력 2 복사4 29 8 7 1예제 출력 2 복사1 7..
백트래킹
https://www.acmicpc.net/problem/15663문제N개의 자연수가 주어지고, M개를 고른 수열을 출력한다.조건1. 중복되는 수열을 출력하면 안된다.조건2. 사전 순으로 증가하는 순서로 출력한다.풀이사전 순으로 출력해야 했기 때문에 입력받은 N들을 sort() 로 정렬했다.2가지를 고려해야 했다.1. 똑같은 조합이 나오면 출력하면 안된다.3 14 4 2위의 입력의 경우, 결과가244 # 중복이여서 안됨 위와 같이 똑같은 수열 4가 중복해서 출력되면 안된다.2. 같은 수가 여러번 나올 수는 있다.아래와 같은 입력의 경우4 29 7 9 1아래와 같이 숫자가 중복 될수는 있다. (9 9)1 71 97 17 99 19 79 9 # 이건 가능 기본적으로 백트래킹을 이용해 풀었다.1의 경우를 해결..
https://www.acmicpc.net/problem/9095문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 소스코드def go(arr): global cnt if sum(arr) == n: cnt += 1 ..
풀이 백트래킹 문제이다. 먼저 입력값으로 주어지는 배열의 크기 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..
