본문 바로가기

브루트 포스/브루트포스(비트마스크)

 (7)
2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 비트마스크는 언제 쓸 수 있는가? map 전체를 움직이고, 전체 경우의 수를 계산할 수 있을 때! 위, 아래, 오른쪽, 왼쪽으로 4가지 경우에 최대 5번 이동 하니까 4 ^ 5 4 ^ 5 = 2 ^ 10 for (int k = 0; k >= 2; 이 조건들 때문에 시간을 너무 많이..
구슬 탈출 2 (중요!!) https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 1. 10번 이하로 움직여서 꺼낼 수 없으면 -1 출력 10보다 커지면 return하면 되겠다. 2. 경우의 수 카운트 같은 방향으로 연속해서 두 번 이동은 의미가 없다. 한 방향으로 이동한 다음, 반대 방향으로 가는 것도 의미가 없다. 이동을 카운트 할 때, 이렇게 씹히는 걸 고려하면 시간이 매우 줄어든다. 애당초 그걸 노리고 낸 문제들이다. 4..
가르침 (어렵다..) https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 모든 단어는 anta로 시작 tica로 끝난다. 그럼 a, n, t, i, c는 무조건 우선 순위로 가르쳐야함 고로 알파벳 개수 26 - 5개 중에 k -5개를 고르는 문제. K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다. 경우의 수가 많지 않으므로 브루트포스로 해결 가능 할 것 같으나?? 26 C k는 k가 26이하 이므로 결국 2의 26승까지 가게된다...
종이 조각 (중요!!!) https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net (1 ≤ N, M ≤ 4) 이므로 최대 2 ^ 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 6..
스타트와 링크 with 비트마스크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include #include using namespace std; int s[20][20]; int n; int main() { cin >> n; for ..
부분 집합의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include using namespace std; int main() { int n; int m; int ans = 0; cin >> n >> m; vector a(n); for (i..
비트마스크 비트 연산 A > B 는 A / 2^B (A + B) / 2 는 (A + B) >> 1 비트마스크 정수로 집합을 나타낼 수 있다! 비트마스크로 문제를 풀 때는 0부터 N - 1까지로 변형을 해서 풀자 추가는 ' | ' 제거는 & ~(1

티스토리툴바