-
[BOJ] 9240 : 로버트 후드
9240 : 로버트 후드 풀이 로테이팅 캘리퍼스 코드 #include<cstdio> #include<algorithm> #include<tuple> #include<vector> #include<cmath> using namespace std; typedef long long ll; typedef pair<int,int> pii; struct POINT{ int x, y; bool operator <(POINT a)const { return x == a.x ? y < a.y : x < a.x; } POINT operator -(POINT a)const { return { x-a.x,y-a.y }; } }; int N; ll sq(int x){ return (ll)x*x; } ll dst(POINT A, POINT B) { return sq(A.x-B.x)+sq(A.y-B.y); } int...
-
[BOJ] 1062 : 가르침
1062 : 가르침 풀이 그냥 완전탐색하면 된다 근데 그냥 하면 시간 초과가 난다 앞뒤에 anta tica를 제거하고 잘 돌려야 한다 코드 #include <bits/stdc++.h> using namespace std; int n, k, dap, a[55]; char s[55]; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) { scanf("%s", s); for (int j = 0; s[j]; j++) a[i] |= (1<<(s[j]-'a')); } int x = (1<<0)|(1<<2)|(1<<8)|(1<<13)|(1<<19); for (int i = x; i < (1<<26);...
-
[BOJ] 16166 : 서울의 지하철
16166 : 서울의 지하철 풀이 잘 짜주면 된다. 비트마스크 썼다. 코드 #include <cstdio> #include <queue> #include <map> using namespace std; int n, en; struct abc { int idx, hosun, cnt; bool operator <(abc a)const { return cnt > a.cnt; } }; map<pair<int, int>, int> cnt; map<int, int> subway; int main() { scanf("%d", &n); for (int i = 1, k; i <= n; i++) { scanf("%d", &k); for (int j = 0, x; j < k;...
-
[BOJ] 1493 : 박스 채우기
1493 : 박스 채우기 풀이 ! 큐브러버님 코드 참고했습니다 ! 가장 큰 큐브부터 사용해서 박스를 채워야 하는 것은 증명할 것도 없이 자명하다. 부피로 으쌰으쌰 슥삭슥삭 멋있게 잘 계산해서 빈 공간을 잘 채워넣으면 된다. 사용했던 큐브를 보다 작은 단위로 쪼개나가자. 1*1*1 단위까지 쪼개지면, 그 큐브의 개수가 박스의 부피와 같은지를 비교해주자. 코드 #include <cstdio> #include <algorithm> typedef long long ll; int l, w, h, n; int a[22]; ll cnt, ans; int main() { scanf("%d %d %d %d",...
-
[BOJ] 12025 : 장난꾸러기 영훈
12025 : 장난꾸러기 영훈 풀이 아 9시 수업 에반데 코드 #include <stdio.h> long long i, k; char s[66]; int main() { scanf("%s %lld", s, &k); k--; for (i = 0; s[i]; i++) { if (s[i] == '6' || s[i] == '7') s[i] -= 5; } while (i--) { if (s[i] == '1' || s[i] == '2') { if (k & 1) s[i] += 5; k >>= 1; } } puts(k ? "-1" : s); return...
-
[BOJ] 1410 : 패턴의 개수
1410 : 패턴의 개수 풀이 bitmask dp를 해보자! 근데 이거 풀이를 어떻게 써야하지 dp[len][bit] = 패턴의 길이를 len까지만 놓고 볼 때, 마스킹 된 패턴에만 일치하는 길이 len짜리 문자열의 수 코드 #include <iostream> #include <string> using namespace std; const int mod = 1000003; int n, k; int dp[50][1 << 15]; string str[15]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> k; for (int i = 0; i < n; i++) cin >> str[i]; int len...
-
[BOJ] 2309 : 일곱 난쟁이
2309 : 일곱 난쟁이 풀이 돌려돌려~ 코드 #include <stdio.h> #include <algorithm> int a[10]; int main() { for (int i = 0; i < 9; i++) scanf("%d", &a[i]); std::sort(a, a + 9); for (int i = 0; i < (1 << 9); i++) { int cnt = 0, sum = 0; for (int j = 0; j < 9; j++) if ((1 << j) & i) cnt++, sum += a[j]; if (cnt != 7 || sum...
-
[BOJ] 1182 : 부분집합의 합
1182 : 부분집합의 합 풀이 완전탐색! dfs로 짜도 되고 n이 작으니까 비트마스킹 해도 된다. 코드 #include <stdio.h> int n, s, ans, a[21]; int main() { scanf("%d %d", &n, &s); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 1; i < (1 << n); i++) { int sum = 0; for (int j = 0; j < n; j++) if (i & (1 << j)) sum += a[j]; ans...
-
[BOJ] 14572 : 스터디 그룹
14572 : 스터디 그룹 풀이 학생들이 아는 모든 알고리즘의 수는 bit OR 연산과 같다. 이는 항상 같거나 증가한다. 모든 학생들이 아는 알고리즘의 수는 bit AND 연산과 같다. 이는 항상 같거나 감소한다. 따라서 누구는 빼고 누구는 넣고 할 것 없이 능력치 조건을 만족하는 범위 내의 모든 학생들을 선택해도 된다. 학생들을 능력치를 기준으로 정렬한 다음, 투 포인터를 사용하면 쉽게 답을 찾을 수 있다. 코드 #include <stdio.h> #include <algorithm> using namespace std; const int n_ = 1e5 +...
-
[BOJ] 14569 : 시간표 짜기
14569 : 시간표 짜기 풀이 모든 경우를 다 돌려보면 된다. bit를 사용하면 편하게 짤 수 있다. 코드 #include <stdio.h> typedef unsigned long long ull; ull t[1001]; int main() { int n, m, k; scanf("%d", &n); for (int i = 0; i < n; i++) { int k, a; scanf("%d", &k); for (int j = 0; j < k; j++) scanf("%d", &a), t[i] |= ((ull)1 << a); } scanf("%d", &m); for (int i = 0; i...