-
[BOJ] 1018 : 체스판 다시 칠하기
1018 : 체스판 다시 칠하기 풀이 그냥 다 돌려보면 된다. 코드 #include <stdio.h> #define min(a,b) (a)<(b)?(a):(b) int n, m, i, j, a, b, ans = 1e9; char str[55][55]; int main() { scanf("%d %d", &n, &m); for (i = 0; i < n; i++) scanf("%s", str[i]); for (i = 0; i < n - 7; i++) for (j = 0; j < m - 7; j++) { int cnt = 0; for (a = i; a...
-
[BOJ] 1450 : 냅색문제
1450 : 냅색문제 풀이 숫자의 크기가 너무 커서 일반적인 냅색 풀이로는 풀 수 없다. 그렇다고 2^30을 돌리자니 그것도 크기가 너무 크다. 수열을 정렬하고 반으로 나눠서 절반씩 완전탐색 해주자. 2^15씩 두 번이니 충분히 돌고도 남는다. 그리고 완전탐색한 두 조합을 linear하게 잘 섞어주자. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int n, c, ans, a[33]; vector<int> v1, v2; void dfs(int s, int e, int sum, vector<int>& v) { if (sum > c) return; 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] 1064 : 평행사변형
1064 : 평행사변형 풀이 hypot(a, b)는 a와 b를 높이, 너비로 하는 빗변의 길이를 구해주는 함수이다. 평행사변형이 만들어질 수 없는 경우를 찾아보자. 둘 이상의 점이 겹치거나, 세 점이 한 직선 위에 있으면 (= 기울기가 같으면) 사각형이 될 수 없다. ccw에서 기울기를 구하는 식을 가져다 쓰자! 여기에 개꿀개꿀 공식이 써있으니 참고하자! 둘 이상의 점이 겹치는 경우도 한 직선 위에 있는 경우이므로 별개로 처리해줄 필요는 없다. (개꿀!) 이제 평행사변형의 둘레의 길이를 찾아보자. 먼저, 남아있는 하나의 점을 찾을 필요가...