문제 링크 http://icpc.me/1192 1192번: 장갑 임의로 왼쪽 통에서 2개, 오른쪽 통에서 8개를 가져온다면 최소한 한 쌍의 같은색의 장갑이 나옴을 보장할 수 있다. www.acmicpc.net 풀이 백트레킹으로 조합을 만들면 된다. 만약 s가 0일때는 아무것도 뽑지 않는 경우가 생길 수 있기 때문에 정답에 -1을 해준다. 코드 #include int n, s, ret; int arr[22]; bool visited[22]; void solve(int cur, int sum) { if (sum == s) ret++; for (int i = cur; i < n; i++) { if (visited[i]) continue; visited[i] = true; solve(i, sum + arr[i]..

문제 링크 http://icpc.me/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 풀이 백트레킹을 이용하여 풀 수 있다. n의 크기가 매우 작으니 백트레킹을 하며 모든 경우를 확인해보면 된다. 코드 #include #include using namespace std; int d[11][11]; int n, m, a, b, c, ans = 1e9, totalSum = 1e9; bool visited[11]; void solve(int cur, int total, i..

문제 링크 http://icpc.me/18429 풀이 3대 500을 찍고 싶은 헬창이라면 누구나 풀어봐야 할 루틴을 정하는 문제이다. 백트레킹으로 모든 경우를 확인하며 풀 수 있다. 코드 #include #include using namespace std; vector v; int n, k, ans; bool visited[10]; void solve(int cur, int sum) { if (sum < 0) return; if (cur == n) { ans++; return; } for (int i = 0; i < n; i++) { if (visited[i]) continue; visited[i] = true; solve(cur + 1, sum + v[i] - k); visited[i] = false;..

문제 링크 http://icpc.me/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 2239번과 2580번이 아예 똑같은 문제인데 왜 두 문제가 있는지는 잘 모르겠다. 한번 풀고 복습까지 하라는 백준님의 말씀이실지도... 이 문제는 백트레킹을 사용하여 풀 수 있다. 모든 행, 열, 박스들에 무슨 수가 들어있는지 미리 저장해 두고 빈칸에 백트레킹을 하며 1~9까지 넣어보면 된다. row [n][k] : n열에 숫자 k가 있다는 의미이다. 그리고 끝까지 도달하면 출력을 하고 더 이상 백트레..

문제 링크 http://icpc.me/9663 풀이 백트레킹을 이용하여 풀이할 수 있다, 백트레킹을 이용하면서 약간의 테크닉이 필요하다. N * N 크기의 배열에 좌표가 있는지 true/false로 저장을 해놓으면 퀸이 놓을 수 있는지 확인하는데 시간이 많이 든다. 한 행에는 하나의 퀸만 놓일 수 있다는 점을 이용하여 크기가 N인 배열만을 이용하여 퀸을 놓을 수 있는지 여부를 확인할 수 있다. visited 배열은 visited[2] = 1이라고 하면 (1, 2)의 점에 퀸이 놓아져 있다는 의미로 사용할 수 있다. 0 ~ n -1 행순으로 채운다고 할떄, 현재 행 x를 채울 때 같은 열에 있는지 확인하는 방법은 0 ~ x-1 행의 값 중 x행에 채울 값과 동일한 값이 있는지 체크하면 된다. 대각선에 놓여..