백트래킹

문제 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 풀이 백트래킹, 브루트포스 알고리즘 연산자의 수는 N - 1로 어떤 연산에서 사용되지 않는 연산자를 생각할 필요가 없고, 전체 연산자를 어떤 순서로 사용할지 정하면 된다. 재귀 함수에서 현재까지 연산한 값(current)과 사용할 피연산자(operands[depth + 1]와 각 연산자의 남아 있는 수를 인자로 받는다. current와 피연산자를 남아 있는 연산으로 계산하고, 사용한 연산자를 1 줄여..

문제 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 구현, 시뮬레이션, 백트래킹 입력된 cctv에서 가능한 모든 상태를 백트래킹으로 탐색하여 해결하였다. cctv 데이터를 다음의 구조체로 vector에 넣어주었다. struct cctv { int x; int y; bool dir[4] = { false, }; }; cctv를 회전할 때는 dir배열을 회전한 만큼 이동하여 구현하였다. for (int dir = 0; dir < 4; ++dir) { bool temp_dir[4] = { false..

문제 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 구현, 브루트포스 알고리즘, 백트래킹 문제를 잘 읽어야 한다. 회전의 순서가 고정적인 것이 아니라, 배열의 최솟값을 구할 수 있도록 회전의 순서를 바꿀 수 있다. 회전의 순서를 정할 수 있도록, dfs를 이용하여 순열 알고리즘을 구현한다. // dfs를 이용한 순열 void dfs(bool select[], int map[], int cnt, int n, int k, vector v) { if (cnt == k) { sol..

문제 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 브루트포스 알고리즘, 너비 우선 탐색, 조합론, 백트래킹 학생은 전체 25명이다. 여기서 자리를 7개 선택하여 문제의 조건이 맞는지 확인하는 방식으로 답을 구한다. 학생의 수가 많지 않기 때문에 브루트포스로 구현해도 시간 초과는 발생하지 않는다. 자리를 선택하는 방법은 백트래킹을 사용한다. 자리 선택과 해제를 반복하며 자리를 7개 선택했다면 현재 상태가 문제의 조건을 만족하는지 확인한다. 문제의 조건은 다음과 같다. 선택한 자리 모두 상하좌우로 연결되어 ..

문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 수학, 브루트포스 알고리즘, 조합론, 백트래킹 사전순으로 출력되어야 하므로 미리 입력받은 문자를 정렬시킨 후에 시작한다. 문자열의 길이는 최대 15로 모든 경우의 수를 탐색해도 시간 초과가 발생하지 않는다. 정렬된 문자열의 앞의 문자부터 선택과 선택해제를 반복하며, 선택된 문자열의 길이가 L이라면 정답 조건을 만족하는지 확인한다. 백트래킹으로 문자를 선택한다. void dfs(int index) { // 선택한 문자의 수가 L에 충족한다면 조건에 맞는지 검..

문제 풀이 백트래킹을 이용한, 구현, 시뮬레이션, 완전 탐색 문제이다. 궁수 3명을 배치하는데는 백트래킹을 사용한다. 배치를 완료하면 게임을 시작한다. 턴마다 적이 아래로 이동하는 것 보다, 궁수가 위로 이동하는 것이 더 간단하다. 각 궁수가 공격할 3명의 적을 탐색한다. 판을 하나하나 검사하면서 적일 경우 현재 궁수와의 거리를 측정한다. 현재까지 검색한 궁수와의 최소 거리보다 현재 측정한 거리가 더 가깝다면 타겟을 변경한다. 같다면 타겟들의 y값을 비교하여 더 작은 y값을 가진 타겟을 선택한다. 선택된 적은 중복되면 안 되므로 set에 저장된다. 선택된 타겟들을 공격하고 현재까지 처치한 적을 갱신한다. 궁수줄을 한 칸 위로 이동한다. 코드 #include #include #include #include..

문제 풀이 백트래킹을 사용한다. 행별로 입력된 숫자, 열별로 입력된 숫자, 블럭 별로 입력된 숫자에 해당하는 배열을 생성하고 관리한다. 스도쿠 칸의 0번째 부터 시작한다. 현재 검사하는 칸을 1씩 증가시켜서 검사한다. 현재 검사하는 칸의 행은 (current / 9)이며, 검사하는 칸의 열은 (current % 9)이다. 검사하는 칸이 0이라면 1부터 9까지의 숫자 중 현재 배열에 입력되지 않은 값으로 설정하고, 다음 칸으로 넘어간다. 검사하는 칸이 0이 아니라면 다음 칸으로 넘어간다. 현재 칸의 검사를 마치면 백트래킹을 실시한다. 코드 #include using namespace std; int ground[9][9]; bool num_vertical[10][9]; // 행 숫자 입력된 것 bool n..

문제 풀이 DFS와 백트래킹을 사용한다. 지나온 알파벳을 확인할 vector를 생성하여 다음으로 지나갈 칸을 확인한다. 코드 #include #include #include using namespace std; int R, C; char board[21][21]; int move_x[4] = { 0, 0, 1, -1 }; int move_y[4] = { 1, -1, 0, 0 }; int answer = 0; void dfs(int x, int y, int dist, vector& alphabets) { answer = max(answer, dist); bool flag = false; for (int i = 0; i < 4; ++i) { int next_x = x + move_x[i]; int next_..

문제 풀이 N이 100000으로 하나하나 비교하면 시간초과 MBTI의 종류는 16가지로 서로 최대한 MBTI가 다르도록 배치한다면 N이 16일 때, 모두가 다른 MBTI를 가진다. N이 16을 초과한 경우에 최대한 MBTI가 다르도록 배치한다면 2명은 같은 MBTI를 가진다. 같은 원리로 N이 32를 초과한 경우에 최대한 MBTI르 다르도록 배치한다면 3명은 같은 MBTI를 가지므로 N이 32를 초과한다면 결과는 0이 된다. N이 32이하인 경우는 탐색이 필요하다. 코드 #include #include #include #include using namespace std; vector MBTIs; vector mini_MBTIs; int mini = INT_MAX; // MBTI가 다른 자리마다 +1 in..