백트래킹
[백준 - 12101] 1, 2, 3 더하기 2 [C++]
1. 문제 https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 2.풀이과정 문제의 설명대로 정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하면 된다. 4를 1, 2, 3의 합으로 나타내는 방법을 사전순으로 정렬하면 아래와 같다. 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 [코드설명] dfs함수는 n을 1, 2, 3의 합으로 나타내는 경우의 수를 생성하며 k번째로 오는 식을 출력한다. 3. 코드 #inc..
[백준 - 15658] 연산자 끼워넣기 (2) [C++]
1. 문제 https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 2. 풀이과정 모든 수의 사이에 연산자를 끼워 넣을 수 있는 모든 경우에 대해서 식의 결과의 최대, 최소를 구한다. [코드설명] dfs함수는 모든 수의 사이에 연산자를 끼워 넣을 수 있는 모든 경우에 대해 탐색한다. 주의해야 할 점은 최대값, 최소값을 저장하는 변수의 초기값을 잘 설정해줘야 하는 것이다. 연산자를 어떻게 끼워넣어..
[백준 - 15666] N과 M (12) [C++]
1. 문제 https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 풀이과정 N과 M (11)문제에서 아래의 조건만 추가된 문제이다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다 N과 M (11) 설명 : https://poisson-it.tistory.com/28 [코드설명] N과 M (11)코드에 한줄만 추가해주면 된다. dfs함수내에서 if(v...
[백준 - 15665] N과 M (11)
1. 문제 https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 풀이과정 1. N개의 자연수 중에서 M개를 고른 수열 2. 같은 수를 여러 번 골라도 된다. 3. 중복되는 수열을 여러 번 출력하면 안 된다. 4. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 위의 네 가지 조건을 만족해야한다. 3번 조건을 만족하기 위해 같은 레벨에서 같은 수를 중복 방문하지 않아야한다. 4번 조건을 만족하기 위해 N개의 수를 오름차순 정렬해줘야한다. ..
[백준 - 15664] N과 M (10) [C++]
1. 문제 https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 풀이과정 N과 M (9)문제에서 아래의 조건만 추가된 문제이다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다 N과 M (9) 설명 : poisson-it.tistory.com/23 [코드설명] N과 M (9)코드에 한줄만 추가해주면 된다. dfs함수내에서 if(v.size() && v..
[백준 - 15663] N과 M (9) [C++]
1. 문제 https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 풀이과정 N개의 자연수 중에서 M개를 고른 수열을 출력하는 문제인데, 아래의 조건들을 만족해야한다. 1. 중복되는 수열을 여러 번 출력하면 안된다. 2. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. N = 4, M = 2 N개의 수 = {9, 7, 9, 1}일 때, 1 7 1 9 7 1 7 9 9 1 9 7 9 9 가 출력되어야 한다. 2번 조건을 만족하기 위해 N개의 수..