백트레킹2 [백준 15683] 감시 www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net backtracking을 사용한 구현문제이다. 어렵다 흑흑 전체 사무실 크기가 8 * 8 이므로 모든 cctv의 경우의 수를 따져야 한다. 구현한 함수는 크게 3가지로 백트래킹 함수 / 씨씨티비로 확인하는 함수 / 사각지대를 카운트하는 함수이다. 입력을 받으며 cctv는 위치와 타입에 대해 배열로 따로 저장해두고 모든 cctv에 대해 rotate를 실시해서 가장 작은 사각지대를 도출한다. 백트래킹 함.. 2020. 12. 16. [백준 1182] 부분수열의 합 www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 벡터를 사용하지 않고 풀어보기! s=0일 경우 하나도 안더했을 때도 포함되므로 빼줘야 한다. 왜냐면 부분 수열의 크기가 양수이기 때문이다. #include using namespace std; int arr[21]; int n, s, answer; void dfs(int idx, int sum) { if (idx > n - 1) { if (sum == s) { answer++.. 2020. 11. 5. 이전 1 다음