궤도

문제 풀이 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] =..