노는 게 제일 좋아

이것도 아주 중요한 문제라고 할 수 있다. 중복되는 값을 어떻게 골라내느냐이다. https://www.acmicpc.net/problem/1039 #맞은 풀이 #include #include #include #include using namespace std; int N, M, K; int ans; set check[11]; //★★★★★★★ void func(string s, int cnt) { string after = s; int x = stoi(s); //string으로 받은 숫자. //K번 바꿨을 때. if (cnt == K) { ans = max(x, ans); return; } //바꿀 수 있는 모든 경우의수 확인 for (int i = 0; i < M - 1; i++) { for (int ..

백트래킹에서 그래도 조건이 많이 붙어서 가지치기를 어떻게 하는지 공부할 만한 문제다. 행과 열 처리는 어떻게든 가능하지만 3*3이 어느 칸인지 찾는 것을 조금 고민해볼 필요는 있다. 결국 1~3까지 첫 째 4~6까지 두 번째.. 이렇게 생각하면 어떻게 할 지 감이 온다. https://www.acmicpc.net/problem/2580 #맞은 풀이 #include #include using namespace std; int pane[9][9]; // 9*9 게임판 bool check = false; // 답을 찾았는지 체크 vector vec; // 채워야 할 곳의 좌표 int number = 0; // 채워야 할 곳의 개수 //조건 1.가로의 합 45, 2.세로의 합 45, 3.3*3 내의 합 45 를..

백트래킹 중에 가장 중요한게 시간인데 백트래킹을 가지치기해서 최대한 시간을 줄여야한다. 왜냐하면.. 백트랙킹은 가짓수가 기하급수적으로 늘어난다. 싹수가 노랗다면 없애야하듯이 가지쳐야한다. https://www.acmicpc.net/problem/15686 #맞은 풀이 #include using namespace std; const int MAX = 51; int N, M; // int node[MAX][MAX]; int ans = INT_MAX; vector chicken; vector house; bool checked[51][51]; vector chosen; //idx가 있는 이유. 이미 골라본 것은 다시 고르지 않음. void func(int cnt, int idx){ if(cnt == M){ /..

어렵지 않았다. 다만 머리로 아 어떡하지? 중복제거 어떡하지?? set 생각날 때까지 어려웠다. https://www.acmicpc.net/problem/5568 #맞은 풀이 #include using namespace std; int n,k; set numbers; vector card; bool check[10]; //카드를 고르면서 정수를 만듬. void func(int cnt, string s){ if(cnt == k){ numbers.insert(stoi(s)); //1,3 과 13은 자리를 바꿔도 같은 정수라 중복 제거해야함. //set 이용 return; } for(int i=0; i> n >> k; for(int i=0; i> x; card.push_back(x); } func(0,"");..

시간초과가 왜 난지 몰랐지만.. 그냥 나중에 생각해보니 날만했었다. https://www.acmicpc.net/problem/1062 #맞은 풀이 #include #include #include #include using namespace std; bool alpha[26]; int N, K; vector vec; int ans = 0; //idx를 추가시켜서 시간을 단축 시켰다. //여기서 idx는 for문이 시작하는 번호를 말한다. void func(int cnt, int idx) { //K-5개만큼 골랐다면 if (cnt == K-5) { int cnt = 0; //각 단어를 읽을 수 있는지 조사 for (string str : vec){ bool read = true; //만약 모르는 글자가 나오..

음.. 생각은 빨리했는데.. 오래걸림.. 왜냐면.. 초기화를 잘못했다. 아...내 1시간반 https://www.acmicpc.net/problem/14502 그렇게 어렵지 않았다. 벽을 무작위로 세워야 하는 것을 이미 알기에.. Brute Force를 해야하는 것은 알았지만 그냥 백트래킹 복습삼아 적용했다. 가장 처음 제출한 풀이.. #include #include #include #define X first #define Y second using namespace std; int map[8][8]; int visited[8][8]; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N,M; int ans = 64; stack stk; // DFS 스택 ve..