Baekjoon/[6] 백트래킹12 [백준] 1182번 부분수열의 합 JAVA (자바) 풀이 문제 1182번 : N개의 정수로 이루어진 수열 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하기 [입력] : 첫 줄에 정수 개수 N, 정수 S (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 수열이 공백으로 구분[출력] : 합이 S가 되는 부분수열 개수 출력 [과정] - [공통] 공집합일 경우를 생각해야 하므로 S = 0 이라면 -1 하고 시작한다 - 재귀적 백트래킹반복문을 쓰지 않아서 좀 더 직관적으로 코드를 간결하게 볼 수 있다dfs(next,sum); dfs(next,sum+arr[start]); 예) [3, 7, 2] / S=9 backtrack(0, 0) ├.. 2023. 11. 27. [백준] 15649번 N과 M(1) JAVA (자바) 풀이 문제 15649번 (백트래킹) : 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 골라서 수열을 모두 구하는 프로그램 (예) N = 3, M = 1 인 경우 1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다 1 / 2 / 3 이렇게 만든 수열을 한줄에 하나씩 출력한다 [입력] : 첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8)[출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X) 수열의 원소는 공백으로 구분해서 출력 : 수열은 사전 순으로 증가하는 순서로 출력 [과정] 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 문제 조건) 숫자 중복금지 → 완전 탐색이 아닌.. 2023. 11. 13. 이전 1 2 다음
