-
[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에서 기울기를 구하는 식을 가져다 쓰자! 여기에 개꿀개꿀 공식이 써있으니 참고하자! 둘 이상의 점이 겹치는 경우도 한 직선 위에 있는 경우이므로 별개로 처리해줄 필요는 없다. (개꿀!) 이제 평행사변형의 둘레의 길이를 찾아보자. 먼저, 남아있는 하나의 점을 찾을 필요가...
-
[BOJ] 13269 : 쌓기나무
13269 : 쌓기나무 풀이 앞에서 보이는 최대 값들로 채워준 다음 옆에서 보이는 최대 값들을 만족하게 바꿔준다 그리고 조건을 만족하는지 체크해보자! 코드 #include <stdio.h> #define REP(k,n) for(k=0;k<n;k++) #define RRP(k,n) for(k=n-1;k>=0;k--) int main() { int n, m, i, j, a[500][500], b[500], c[500]; scanf("%d %d", &n, &m); REP(i,n) REP(j,m) scanf("%d", &a[i][j]); REP(j,m) { scanf("%d", &b[j]); REP(i,n) if (a[i][j] == 1) a[i][j] = b[j]; } RRP(i,n) { scanf("%d", &c[i]); REP(j,m) if (a[i][j] > c[i]) a[i][j] = c[i]; } REP(j,m)...
-
[BOJ] 13268 : 셔틀런
13268 : 셔틀런 풀이 달빛이 흡사 비오듯 쏟아지는 밤에도 우리는 헐어진 성(城)터를 헤매이면서 언제 참으로 그 언제 우리 하늘에 오롯한 태양을 모시겠느냐고 가슴을 쥐어뜯으며 이야기하며 이야기하며 가슴을 쥐어뜯지 않았느냐? 코드 #include <stdio.h> #include <stdlib.h> #define a(e) for(int i=1;i<=e;i++)n-=5,f(i) #define b(e) for(int i=e;i>=1;i--)n-=5,f(i) int n, k; void f(int a) { if (n <= 0) { printf("%d", a); exit(0); } } int main() { scanf("%d", &n); n %= 100; for (int j = 0; j <= 4;...
-
[BOJ] 13560 : 축구게임
13560 : 축구게임 풀이 랑주의 정리! S[i] = a[1~i]의 합, S[1~k] >= kC2 S[n] = nC2 증명 코드 #include <stdio.h> #include <algorithm> int main() { int n, i, s = 0, a[10000]; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); std::sort(a, a + n); for (i = 0; i < n; i++) { s += a[i]; if (s < (i+1)*i/2) return ~printf("-1"); } printf("%d", s == n*(n-1)/2 ? 1 : -1);...
-
[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...