궤도

문제 풀이 dp로 풀면 더 빨리 풀 수 있을텐데 난 그냥 완전탐색(브루트포스)으로 풀었다. 문제를 풀고 보니 dfs를 사용한 코드가 많았다. 근데 뭔가 논리가 그냥 이대로 dp 쓰면 되는거 아닌가 싶긴 했다. 소스코드 #include #include #include using namespace std; int N, money, result; vector input; void backtracking(int idx) { if (money > result) //최대 비용 비교 result = money; for (int i = idx; i N; for (int i = 0; i > dur >> profit; in..

문제 풀이 백트래킹으로 탐색하면서 S가 되는 값이 나오는지 확인하면 된다. 부분수열의 길이가 정해진건 아니라 이와 관련된 종료조건은 딱히 없다. S와 같은 부분수열의 합을 찾자마자 return을 하는 실수를 할 수도 있다. 근데 만약 S=0이고 주어진 정수가 -7 7 -3 3이라면 -7 7도 가능한 부분수열이지만 -7 7 -3 3도 가능한 부분수열이다. 이걸 놓치지 않도록 하자. 소스코드 #include using namespace std; int input[20], N, S, sum, cnt; void backtracking(int idx) { for (int i = idx + 1; i < N; i++) { //중복되는 수열을 제거하기 위해 sum += input[i]; //visited 처리 if (..

문제 풀이 사전순으로 출력하라고 했으니까 일단 문자 입력을 정렬해야할 것이다. 백트래킹으로 C길이의 문자열을 만들고, 이 문자열이 모음 1개 이상, 자음 2개 이상의 규칙을 충족하는지 확인하면 된다. 소스코드 #include #include using namespace std; int L, C; char input[15], arr[15]; bool isPromising() { int vowel = 0; for (int i = 0; i = 1) && ((..

문제 풀이 보통의 최단거리 문제와 달리 TSP 문제는 처음 출발지점으로 돌아와야 한다. 그냥 백트래킹으로 경로를 끝까지 찾다가 마지막 지점에서 처음 출발지점으로 돌아올 수 있는 길이 있는지만 확인하면 된다. 소스코드 #include using namespace std; int matrix[10][10], N, cost, min_cost = -1; bool visited[10]; //실시간으로 값을 갱신하는 코드는 갱신을 취소하는 부분을 반드시 넣어야 함 void backtracking(int start, int cur, int num) { if (num == N) { //종료 조건 if (matrix[cur][start] != 0) { //처음 시작점으로 돌아올 수 있는가? cost += matrix[c..

문제 풀이 dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다. 3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호출한다. 소스코드 #include using namespace std; int cnt; void backtracking(int num) { if (num == 0) { //0이면 카운트 추가 cnt++; return; } for (int i = 3; i >= 1; i--) { //3부터 1까지 뺄 수 있는지 확인 if ((num - i) >= 0) backtracking(num - i); } } int main() { int t, n; cin >> t; for (int i = 0; i > n; backtracking(n)..

문제 풀이 가능한 모양을 하나하나 분리해서 찾는건 이 문제가 브루트포스라고 해도 너무한 방법이다. 보라색 조각을 제외한 나머지 4개의 조각은 백트래킹으로 탐색할 수 있는 조각이다. 백트래킹으로 탐색할 수 있다는걸 쉽게 설명하면 한붓 그리기처럼 탐색할 수 있단 뜻이다. 그럼 보라색 조각을 제외한 나머지 조각은 백트래킹으로 처리한다고 치고, 보라색 조각은 어떻게 처리할까? 이런 조각 하나가 있다고 하자. 이 조각을 기준으로 상하좌우에 조각을 붙이면 이런 + 모양이 될 것이다. 여기에 상하좌우 중 하나의 조각만 빼면 가능한 모든 보라색 조각의 경우가 나올 것이다. 소스코드 링크 = 0) && (nr = 0) && (nc < M)) { //범위에 들어오면 저장 cnt++; arr[i] =..

문제 풀이 팀을 나누는게 가장 중요한 문제이다. 6명이 있을 때 3명을 고르고 나면 선택받은 3명은 스타트팀 선택받지 못한 3명은 링크팀에 넣어 계산하면 될 것이다. 근데, (1,2,3)번 사람을 고르는 것과 (2,1,3)번 사람을 고르는 것은 같은 경우이다. 이런 경우를 어떻게 제외할 수 있을까? myunji.tistory.com/198?category=1154147 [백준] 15650번 : N과 M (2) 문제 풀이 myunji.tistory.com/73?category=1154147 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇.. myunji.tistory.com 위 문제는..

문제 풀이 숫자의 순서는 고정되어 있으니 백트래킹의 대상이 되는 것은 사칙연산 기호 뿐이다. 종료 조건을 만나면 함수를 종료하던 이전 문제들과 달리 노드의 끝에 다다르면 최댓값, 최솟값을 갱신하며 모든 경우의 수를 따져야 한다. 소스코드 #include using namespace std; int min_num = 1000000000; int max_num = -1000000000; int arr[11]; int op[4]; int N; int cal(int a, int b, int op) { //계산 int result = 0; switch (op) { case 0: result = a + b; break; case 1: result = a - b; break; case 2: result = a * b..