백트래킹

유형 난이도 완료일 링크 특이사항 백트래킹 실버2 23.04.04 https://www.acmicpc.net/problem/16953 내 코드 #include using namespace std; int a, b; int MIN = 1000000000; void DFS(long long int n, int depth) { if(n == b && depth b) return; DFS(n*2, depth+1); DFS(n*10+1, depth+1); } int main(void) { cin >> a>> b; DFS(a,1); if(MIN == 1000000000) MIN = -1; cout

유형 난이도 완료일 링크 특이사항 백트래킹 실버2 23/04/03 https://www.acmicpc.net/problem/11725 내 코드 #include #include #include using namespace std; vector vv; vector v; int v1, v2; int arr[100001]; int visited[100001]; int n; void DFS(int parent, int me) { arr[me] = parent; visited[me] = 1; for(int i=0; i < vv[me].size(); i++) { if(visited[vv[me][i]]==1) continue; DFS(me, vv[me][i]); } } int main(void) { ios_base::..

유형 난이도 완료일 링크 특이사항 백트래킹 실버2 23/04/03 https://www.acmicpc.net/problem/15666 내 코드 #include #include #include using namespace std; int arr[10001]; int n, m; vector box; void DFS(int idx, int depth) { if(depth > m) { for(int a: box) cout k; arr[k]+=10001; } DFS(0,1); } 이전 문제 N과M(9)와 다른 점은 같은 수를 여러번 사용해도 되며 수열이 비내림차순이어야 한다는 점 이었다. 같은 수를 여러번 사용할 수 있으므로 중복된 입력을 받아도 한 번만 입력 받은 것과 차이가 없다. 따라서 한 번 입력 받았을 ..

유형 난이도 완료일 링크 특이사항 백트래킹 실버2 23/03/31 https://www.acmicpc.net/problem/15663 내 코드 #include #include #include using namespace std; int arr[10001]; int n, m; vector box; void DFS(int idx, int depth) { if(depth > m) { for(int a: box) cout k; arr[k]++; } DFS(0,1); } 이전 문제들과 달리 입력으로 중복된 수가 주어질 수 있는 문제다. 따라서 숫자들을 입력 받아 배열에 저장하는 방식이 아닌 숫자 범위인 10000까지를 인덱스로 갖는 배열을 만들어 숫자가 입력될 때마다 그 값에 +1 하는 것으로 대체하였다. 값이 ..

유형 난이도 완료일 링크 특이사항 백트래킹 실버3 23/03/31 https://www.acmicpc.net/problem/15657 내 코드 #include #include #include using namespace std; int arr[8]; int n, m; int visited[8]; vector box; void DFS(int idx, int depth) { if(depth == m) { for(int i=0;i

유형 난이도 완료일 링크 특이사항 백트래킹 실버3 23/03/30 https://www.acmicpc.net/problem/15654 내 코드 #include #include #include using namespace std; int arr[8]; int n, m; int visited[8]; vector box; void DFS(int idx, int depth) { if(depth == m) { for(int i=0;i

출력값은 올바르게 나오는데 계속 6%에서 틀렸다고 해서 오랫동안 고민했다. 시간 초과면 몰라도 틀렸다고 하는 이유를 알 수 없었다. 질문글들을 찾아보다가 출력값이 모두 올바른데 틀렸다는 것은 index 범위 오류라던가 메모리 초과 오류 등 Undefined Behavior와 관련있을 것이라는 댓글을 보았고 내 코드에서 그럴 위험이 있는 부분들을 생각해보았다. #include #include #include #include using namespace std; // 퀸 후보 위치 선정 후 조건 만족하는지 확인 -> 수직/대각 연장선상에 퀸이 없는지 확인(n*n개 중 n개를 선정하는 모든 경우의 수를 반복) // OR 후보 위치를 선정할 때 한 위치 선정하면 그 다음은 앞선 퀸의 수직/대각 연장선을 피해서 ..