컴굥일지

문제 https://www.acmicpc.net/problem/15663 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전순으로 증가하는 순서대로 출력해야 하며, 수열이 중복되면 안 된다. 하지만, 입력으로 주어지는 원소 N개 사이에는 중복이 있을 수 있다. 문제 풀이 N과 M (5)과 다르게 N과 M (9)는 입력받은 원소가 중복이 존재할 수 있다. 따라서 n=3, m=2, [10,10,9]를 입력받았을 때 아래와 같이 출력되어야 한다. 9 10 10 9 10 10 [9,10]이나 [10,9]가 2번 출력되면 절대 안 된다. 하지만 이 문제에서 set을 사용하여 중복을 제거하면 안 된다. set은 기본적으로 사전순 정렬이 되기 때문에, 위의 예시의 경우..

문제 https://www.acmicpc.net/problem/15657 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 고르는 자연수는 서로 중복이어도 상관없으나, 비내림차순 수열이어야 한다 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 문제 풀이 N과 M (7)과 다르게 N과 M (8)는 수열이 비내림차순이어야 한다는 조건이 추가되었다. 따라서, N과 M (6)처럼 이전에 어떤 값을 선택했는지도 같이 인자로 넘겨주어야 한다. 또한, N과 M (7)처럼 원소의 중복을 허용하기 때문에 used 배열을 쓸 이유가 없다. [BOJ/백준 15655][C++] N과 M (6) 문제 https://www.acmicp..

문제 https://www.acmicpc.net/problem/15656 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 고르는 자연수는 서로 중복이어도 상관 없다. 문제 풀이 N과 M (5)과 다르게 N과 M (7)는 수열의 원소가 중복이어도 된다는 조건이 추가되었다. 그렇기 때문에 굳이 used 배열로 사용 여부를 판단할 필요가 없다. [BOJ/백준 15654][C++] N과 M (5) 문제 https://www.acmicpc.net/problem/15654 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전순으로 증가하는 순서대로 출력해야 한다. 문제 풀이 N과 M (1 gyong0117.tistory.com 코..

문제 https://www.acmicpc.net/problem/15655 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전순으로 증가하는 순서대로 출력해야 하며, 수열은 오름차순이어야 한다. 문제 풀이 N과 M (5)과 다르게 N과 M (6)는 수열이 오름차순이어야 한다는 조건이 추가되었다. N과 M (5)은 몇 개를 선택했는지만 인자로 넘겨서 종료조건을 체크하면 되었지만, N과 M (6)는 오름차순 수열을 만들어야 하기 때문에, 이전에 어떤 값을 선택했었는지에 대한 정보도 넘겨주어야 한다. (값 자체가 아니라, 그 값의 인덱스를 넘겨준다.) 오름차순을 유지하기 위해 이전에 선택한 값의 인덱스를 받아, 그 이후 값부터 for문을 돌기 때문에 used 배열..

문제 https://www.acmicpc.net/problem/15654 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전순으로 증가하는 순서대로 출력해야 한다. 문제 풀이 N과 M (1)과 다르게 N과 M (5)는 N개의 원소를 입력으로 받아와야 한다는 차이가 있다. 입력은 정렬된 상태로 주어지지 않기 때문에, backtracking을 하기 전에 정렬을 해줘야 한다. [BOJ/백준 15649][C++] N과 M (1) 문제 https://www.acmicpc.net/problem/15649 문제 내용 1~N 까지의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전 순으로 증가하는 순서대로 출력해야 한다. 문제 풀이 N과 M은 백 ..

문제 https://www.acmicpc.net/problem/15652 문제 내용 1~N까지의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 고르는 자연수는 서로 중복이어도 상관없으나, 비내림차순 수열이어야 한다 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 문제 풀이 N과 M (3)과 다르게 N과 M (4)는 수열이 비내림차순이어야 한다는 조건이 추가되었다. 따라서, N과 M (2)처럼 이전에 어떤 값을 선택했는지도 같이 인자로 넘겨주어야 한다. 또한, N과 M (3)처럼 원소의 중복을 허용하기 때문에 used 배열을 쓸 이유가 없다. [BOJ/백준 15650][C++] N과 M (2) 문제 https://www.acmicpc...

문제 https://www.acmicpc.net/problem/15651 문제 내용 1~N까지의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 고르는 자연수는 서로 중복이어도 상관 없다. 문제 풀이 N과 M (1)과 다르게 N과 M (3)는 수열의 원소가 중복이어도 된다는 조건이 추가되었다. 그렇기 때문에 굳이 used 배열로 사용 여부를 판단할 필요가 없다. [BOJ/백준 15649][C++] N과 M (1) 문제 https://www.acmicpc.net/problem/15649 문제 내용 1~N 까지의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전 순으로 증가하는 순서대로 출력해야 한다. 문제 풀이 N과 M은 백 gyong0117.tistory.com 코드 ..

문제 https://www.acmicpc.net/problem/15650 문제 내용 1~N까지의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열은 오름차순이어야 하며, 사전 순으로 증가하는 순서대로 출력해야 한다. 문제 풀이 N과 M (1)과 다르게 N과 M (2)는 수열이 오름차순이어야 한다는 조건이 추가되었다. N과 M (1)은 몇 개를 선택했는지만 인자로 넘겨서 종료조건을 체크하면 되었지만, N과 M (2)는 오름차순 수열을 만들어야 하기 때문에, 이전에 어떤 값을 선택했었는지에 대한 정보도 넘겨주어야 한다. 또한, 오름차순을 유지하기 위해 이전에 선택한 값을 받아, 그 이후 값부터 for문을 돌기 때문에 used 배열도 필요 없다. [BOJ/백준 15649][C++] N과 M (..

문제 https://www.acmicpc.net/problem/15649 문제 내용 1~N 까지의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전 순으로 증가하는 순서대로 출력해야 한다. 문제 풀이 N과 M은 백트래킹의 대표적인 문제이다. N과 M (1)은 몇 개를 선택했는지만 인자로 넘겨서 종료조건을 체크하면 된다. 코드 #include #include using namespace std; int n, m; vector used(9, false); vector result(8, 0); void back(int cnt) { // 몇개를 선택했는지 if (cnt == m) { for (int i = 0; i < m; i++) { cout m; back(0); }

문제 https://www.acmicpc.net/problem/1182 문제 내용 N개의 정수로 이루어진 수열의, 크기가 양수인 부분집합 중에 합이 S인 경우의 수를 구하면 된다. 문제 풀이 모든 원소는 2가지로 구분된다. 부분수열에 포함되거나, 포함되지 않거나. 각 원소에 대해 포함된 경우와 포함되지 않는 경우를 계산해보면 된다. 단, 합이 0일 때는 모든 원소를 포함시키지 않는 경우(공집합)도 포함되므로, 개수에서 -1을 해줘야 한다. 코드 #include using namespace std; int arr[20]; int n, s; int cnt = 0; void back(int current, int ssum) { if (current == n) { if (ssum == s) { cnt++; } ..