-
[BOJ] 14888 : 연산자 끼워넣기
14888 : 연산자 끼워넣기 풀이 완전탐색 완전탐색 신나는 노래~ 코드 #include <stdio.h> int n, i, mn = 2e9, mx = -2e9, a[11], op[4]; void dfs(int c, int v) { if (c == n) { mn = mn < v ? mn : v; mx = mx > v ? mx : v; return; } if (op[0]) --op[0], dfs(c + 1, v + a[c]), ++op[0]; if (op[1]) --op[1], dfs(c + 1, v - a[c]), ++op[1]; if...
-
[BOJ] 1799 : 비숍
1799 : 비숍 풀이 일반적인 풀이로 답을 구하려면 O(2^(10*10))으로 TLE가 난다. 체스판에서 대각선이 흑과 백으로 구분됨을 이용하자. 흑색칸 O(2^(5*5))와 백색칸 O(2^(5*5))를 따로 구해서 더하면 TLE를 피할 수 있다. 앞선 (boj 9663 N-Queen) 풀이에서 언급한 x를 +로 뒤집기(?)를 이용할 수 있겠다. 코드 #include <stdio.h> #define max(a,b) (a)>(b)?(a):(b) int n, f, ans[2], l[33], r[33], a[33][33]; void dfs(int x, int y, int c) { ans[f] = max(ans[f], c); if (y >= n) y = f ^ (++x %...
-
[BOJ] 9663 : N-Queen
9663 : N-Queen 풀이 룰루랄라 백트래킹을 해주자~ x 모양 대각선을 + 모양으로 뒤집어서 생각할 때 (x, y) -> (x+y, x-y)를 이용하면 편하다. 말이 조금 이상하지만 아무튼 저렇게 넣고 출력해보면 대강 이해 갈 것이다. https://www.acmicpc.net/problem/2496 위 문제도 이 테크닉을 써서 풀 수 있겠다. 코드 #include <stdio.h> int n, ans, u[33], l[33], r[33]; void dfs(int h, int c) { if (c == n) { ans++; return; } for (int i = 0; i < n; i++) {...
-
[BOJ] 1987 : 알파벳
1987 : 알파벳 풀이 마음도 한자리 못 앉아 있는 마음일 때, 친구의 서러운 사랑 이야기를 가을 햇볕으로나 동무 삼아 따라가면, 어느새 등성이에 이르러 눈물나고나. 코드 #include <cstdio> const int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 }; int n, m, k, ch[99]; char s[22][22]; void dfs(int x, int y, int c) { if (k < c) k = c; if (k > 25) return; ch[s[x][y]] = 1; for (int i = 0; i...
-
[BOJ] 2580 : 스도쿠
2580 : 스도쿠 풀이 태양을 의논하는 거룩한 이야기는 항상 태양을 등진 곳에서만 비롯하였다. 코드 #include <stdio.h> #include <stdlib.h> #include <vector> using namespace std; struct ABC { int x, y, z; }; int a[9][9], x[9], y[9], z[9]; vector<ABC> p; void dfs(int now) { if (now == p.size()) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) printf("%d ", a[i][j]); puts(""); } exit(0); } int nx...