본문 바로가기
반응형

백트래킹2

BOJ 9663 - N-Queen / C++ 링크 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 어짜피 같은 행에는 퀸을 둘 수 없으므로 열들만 확인하면 된다. col 배열을 선언하고 각 col의 값에는 몇 번째 행에 퀸이 있는지 저장한다. 즉, col[0] = 3은 0번째 열, 3번째 행에 퀸을 놓는다는 의미이다. 같은 열에 존재하거나, 기울기가 같다면(대각선에 있다면) 퀸을 둘 수 없다. 이를 계산하여 가능 여부를 리턴하는 check 함수를 선언하고 모든 열을 체크하며 둘 수 있다면 해당 .. 2022. 3. 28.
BOJ 14888 - 연산자 끼워넣기 / C++ 문제 링크 : https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 주석으로 대체 코드 #include #include #include using namespace std; int n, maxVal = -2e9, minVal = 2e9; vector nums; int opers[4]; //덧셈, 뺄셈, 곱셈, 나눗셈 순서 void DFS(int sum, int idx){ if(idx == .. 2022. 3. 28.
반응형

티스토리툴바