가지치기

가지치기 방법

1. 아예 진입 안하기

[문제]

주사위 3개
2, 4 제외 한

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int used[10];
int path[3];
void run(int lev) {
	if (lev == 3) {
		for (int i = 0; i < 3; i++) {
			cout << path[i];
		}
		cout << "\n";
		return;
	}
	for (int i = 1; i <= 6; i++) {
		if (i == 2)continue;
		if (i == 4)continue;
		path[lev] = i;
		run(lev + 1);
		path[lev] = 0;
	}
}

int main() {
	run(0);
	return 0;
}

진입후 나오기

lev 런타임 에러 조심하기!
제일 헷갈리는고,,

sum 구하기

sum이하의 눈금만 출력하기,,
진짜로 안내려가는고,,

1) 원래했던방법,,

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

char path[10];
//10이하 눈금,,
void run(int lev, int sum) {

	if (sum > 10)return;
	if (lev == 3) {
		cout << path << endl;
		return;
	}
	for (int i = 1; i <= 6; i++) {
		path[lev] = i + '0';
		run(lev + 1, sum + i);
		//sum은 계속 갱신되니깐,,
		path[lev] = 0;
	}
}
int main() {

	run(0, 0);
	
	return 0;
}

2)내가 연습해야하는 방법

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

char path[10];
//10이하 눈금,,
void run(int lev, int sum) {

	if (lev == 3) {
		cout << path << endl;
		return;
	}
	for (int i = 1; i <= 6; i++) {
		if (sum + i > 10)continue;
		path[lev] = i + '0';
		run(lev + 1, sum + i);
		//sum은 계속 갱신되니깐,,
		path[lev] = 0;
	}
}
int main() {

	run(0, 0);
	
	return 0;
}

흐음,,, 모르겠다아직 ㅠ

[헷갈렸던거]

char path배열에 숫자넣는고
해결해땨

path[lev]=i+'0';

[문제]

2번째 숫자가 2가 아닌 3자리
1) 아예 진입 안하기

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

char path[10];
//10이하 눈금,,
void run(int lev) {
	
	if (lev == 3) {
		cout << path <<endl;
		return;
	}
	for (int i = 1; i <= 6; i++) {
		if (lev == 1 && i == 2)continue;
		path[lev] = '0' + i;
		run(lev + 1);
		path[lev] = 0;
	}
}
int main() {

	run(0);
	
	return 0;
}

2)진입했다가 나오기

#include <iostream>

using namespace std;

char path[10];
void run(int lev) {
	if (path[1] == '2')return;
	if (lev == 3) {
		cout << path <<endl;
		return;
	}
	for (int i = 1; i <= 6; i++) {
		path[lev] = '0' + i;
		run(lev + 1);
		path[lev] = 0;
	}
}
int main() {

	run(0);
	
	return 0;
}

[문제]
연속으로 같은거 2개 나오지 않게 하기
1) 진입후 나오기

#include <iostream>

using namespace std;

char path[10];
void run(int lev) {
	if (lev>=2 && path[lev - 2] == path[lev - 1])return;

	if (lev == 3) {
		cout << path <<endl;
		return;
	}
	for (int i = 1; i <= 6; i++) {
		path[lev] = '0' + i;
		run(lev + 1);
		path[lev] = 0;
	}
}
int main() {

	run(0);
	
	return 0;
}

2)아예 진입 안하기

#include <iostream>

using namespace std;

char path[10];
void run(int lev) {

	if (lev == 3) {
		cout << path <<endl;
		return;
	}
	for (int i = 1; i <= 6; i++) {
		if (lev >0 && path[lev - 1] == i+'0')continue;
		path[lev] = '0' + i;
		run(lev + 1);
		path[lev] = 0;
	}
}
int main() {

	run(0);
	
	return 0;
}

백트래킹

뒤로 탐색한다.
답이 아닌 곳은 과감하게 컷하고 돌아간다.. 돌아가서 모든경우를 보는경우

모든경우는 다 때려맞추는데, 잘못된 부분은 컷 하는것!!

[문제]