백트랙킹

문제 : https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 어떤 문제인가? 배열이 있을 때 | A [0] - A [1] | + | A [1] - A [2] | +... + | A [N-2] - A [N-1] |의 값이 최대가 되게 배열을 재배치해야 한다. 배열을 재배치하고 난 후 얻을 수 있는 최댓값을 출력하면 된다. 접근 방법 숫자를 재배치하기 위해서는 어떤 숫자를 어디에 배치해야 할지를 결정해야 한다. 따라서 데이터는 앞, 뒤 삭제 삽입 연산이 간편한 de..

문제 : https://www.acmicpc.net/problem/16457 16457번: 단풍잎 이야기 첫째 줄에 키의 개수 n, 퀘스트의 개수 m, 퀘스트 당 사용해야 하는 스킬의 수 k가 주어진다. n은 10 이하, k는 n 이하의 양의 정수이며, m은 100 이하의 양의 정수이다. 둘째 줄부터 m개의 줄에는 각각 www.acmicpc.net 어떤 문제인가? m개의 퀘스트가 존재한다. 각 퀘스트는 k개의 스킬을 써서 완료할 수 있다. 1부터 2*n까지의 정수 중 n개를 뽑는다. 이때의 정수가 퀘스트를 완료할 때 필요한 스킬이다. 이때 퀘스트를 가장 많이 완료할 수 있는 경우를 찾으면 된다. 접근 방법 int n, m, k; int quest[101][10]; 문제에서 주어진 변수와 입력된 퀘스트를 ..

문제 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 어떤 문제인가? 백 트랙킹의 대표적인 문제로 들었다. N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 물어보는 문제이다. 접근 방법 N이 4일 때 (1, 1)부터 퀸을 놓으면서 진행한다. 퀸은 대각선과 직선을 모두 공격할 수 없으므로 한 줄에 퀸이 놓이면 무조건 다음 줄로 넘어가야 한다. 그래서 두 번째 줄로 이동해서 다음 퀸을 놓을 자리를 찾는다. (2, 1), (2, 2)는 ..