전체 글327 BOJ 1182 - 부분수열의 합 N과 M 시리즈에서 사용한 논리를 적용했다. 여러 군데에서 요긴하게 잘 쓸 것 같다. #include #include #include using namespace std; int arr[20], n, s, cnt; void go(vector& picked, int sum) { if (!picked.empty() && sum == s) { cnt++; } int next = picked.empty() ? 0 : picked.back() + 1; for (int i = next; i < n; i++) { picked.push_back(i); go(picked, sum + arr[i]); picked.pop_back(); } } int main() { scanf("%d %d", &n, &s); for (int.. 2019. 7. 6. BOJ 9663 - N QUEEN 저번에 마구잡이로 풀어봤지만 백트래킹 연습으로 한 번 더 풀어봤다. 1번줄부터 n번 줄까지 퀸을 배치하는데, x좌표가 중복되지 않게 뽑는 것을 백트래킹 해주면서 대각선에 다른 퀸이 배치돼있는지 검사해줬다. #include #include #include #include using namespace std; int n; bool isValid(vector& picked) { //대각선 검사만 해주면 된다. |(y'-y)| == |(x'-x)| 인경우 return false if (picked.empty()) return true; for (int i = 0; i < picked.size()-1; i++) { // {i, picked[i]} : 퀸의 위치 (y,x) for (int j = i + 1; j <.. 2019. 7. 6. BOJ 15649 - N과 M (1~12) N개 중 M개를 뽑아 나열하는 경우의 수 시리즈이다. 기본적으로 백트래킹을 이용해서 재귀로 구현함. 9~12같은 경우 중복을 제거해줘야 하는데, 이건 set로 해결하였다. #include #include #include using namespace std; void printPicked(vector& picked) { for (int n : picked) printf("%d ", n + 1); printf("\n"); } int n, m; void pick(vector& picked, vector& isUsed, int k) { if (k == m) { printPicked(picked); return; } for (int next = 0; next < n; next++) { if (!isUsed[nex.. 2019. 7. 6. BOJ 2448 - 별찍기11 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (k ≤ 10) www.acmicpc.net 재귀를 이용해서 풀어주면 된다. boj 2447문제도 재귀를 활용한 별찍기 문제인데 2448이 생각하는데 조금더 시간이 걸렸다. 출력은 잘 되는데 자꾸 틀렸습니다가 떠서 찾아봤더니 백준에선 출력을 읽을때 null을 읽으면 틀렸습니다 처리를 한다고 한다. 가로의 길이가 세로의 길이의 두배인 것을 잘 확인해서 문제를 풀었지만 map[][]을 선언할때 가로길이를 두배로 두지 않아서 1차로 헤맸다. map[][]을 ' '로 fill해줄때 선언한 것에 맞게 여기도 가로길이를 세.. 2019. 7. 4. 이전 1 ··· 76 77 78 79 80 81 82 다음