본문 바로가기

brute force

BOJ)10881 프로도의 선물 포장 문제: icpc.me/10881 세개의 상자를 하나의 큰 포장상자안에 넣어야 할 때 준비해야하는 포장상자의 최소 넓이를 구하는 문제이다. 우선 상자가 세개밖에 주어지지 않기 때문에 완전탐색을 생각해볼 수 있다. 세개의 상자를 배치하는 모양은 회전에 따라서 달라지지 않는 경우는 1열로 3상자를 배치하는 케이스와 2상자 위에 1 상자를 쌓아놓는 모양 두가지 밖에 없다. 때문에 주어진 조건으로 위의 경우에 해당 하는 모든 경우를 탐색하면 하나의 쿼리를 2*6^3의 시간만에 처리할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include using namespace std;pair a[6];int three(i.. 더보기
BOJ)2503 숫자 야구 문제:icpc.me/2503 각 자리의 숫자를 임의로 설정해 준 뒤 매 쿼리를 비교해주는 계산을 하더라도 O(1000*N)의 시간밖에 걸리지 않기 때문에 완전 탐색을 해주어 통과되는 숫자의 수를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include using namespace std;int n, r;struct query { int num, strike, ball; query(int num, int strike, int ball) :num(num), strike(strike), ball(ball) {} query() {} int getfirst().. 더보기
BOJ)1405 미친 로봇 문제: icpc.me/1405 각 방향으로 이동할 확률과 이동 횟수가 주어질 때 경로가 단순할 확률을 구하는 문제이다. dfs를 통한 4방향 탐색으로 각 방향으로 이동할 확률을 곱해서 brute force 해주면 된다. 1234567891011121314151617181920212223242526272829#include #include using namespace std;int n, visited[30][30];double p[4];int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };double dfs(int x, int y, int cnt) { if (cnt == 0)return 1.0; double ret = 0.0; visited[x][y] = true; for .. 더보기
BOJ)1251 단어 나누기 문제: icpc.me/1251 단어를 세 단어로 나눈 뒤 나눈단어를 전부 뒤집어 다시 붙인 단어들 중 사전순으로 가장 앞서는 단어를 출력하는 문제이다. N이 50까지 밖에 안들어오기 때문에 가능한 경우를 전부 뽑아내도 50C3 밖에 안되므로 모든 경우를 탐색하여 결과를 확인해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include #include using namespace std;vector vt;string a;void rev(string &x, int lo, int hi) { string z = x; for (int i = lo; i = a.length() .. 더보기
BOJ)14500 테트로미노 문제:icpc.me/14500 주어진 문제의 답은 모든 경우에 테트로미노를 다 대봄으로서 구할 수 있다. 주어지는 테트로미노의 5가지 모양중 ㅜ 모양을 제외한 4가지 모양은 DFS를 통하여 탐색이 가능하고 ㅜ모양만 따로 처리를 해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include using namespace std;int n, m, a[501][501], v[501][501], r;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };bool chk(int x, int y) { r.. 더보기
BOJ)14502 연구소 문제: icpc.me/14502 N,M의 범위가 매우 적기 때문에 나올 수 있는 경우를 전부 확인해줄 수 있다. 6중 포문을 통하여 모든 경우에 벽을 세워본 후 dfs를 통하여 바이러스가 얼마나 퍼질 수 있는지 조사하여 그 최솟값을 전체 크기에서 벽을 제외한 값에서 빼주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include #include #include using namespace std;int n, m, a[9][9], r, visited[9][9], b;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,.. 더보기
BOJ)7573 고기잡이 문제: icpc.me/7573 그물의 둘레와 물고기의 수가 100으로 매우 적다 이를 이용하여 완전탐색을 해주면 된다. 한 물고기에 대해 그 물고기를 둘레에 포함하는 가능한 모든 그물을 만들어본 뒤 확인해주면 된다. 1234567891011121314151617181920212223242526272829303132333435#include #include using namespace std;int n, l, m, r;pair f[101];bool chk(int x, int y, int lx, int ly, int rx, int ry) { return lx 더보기
BOJ)2992 크면서 작은 수 문제:icpc.me/2992 등장하는 수로 조합가능 한 모든 수를 비교하여 그 중 최솟값을 구해주면 된다. 시간 복잡도는 O(6!)이다. 12345678910111213141516171819202122232425#include #include #include #include #define INF 987654321using namespace std;char a[7];int r = INF;int main() { scanf("%s", &a); int v = stoi(a); vector vt; for (int i = 0; a[i] != '\0'; i++) vt.push_back(a[i]); sort(vt.begin(), vt.end()); do { for (int i = 0; i 더보기
BOJ)12100 2048 (Easy) 문제:icpc.me/12100 2048 게임에서 가능한 5번의 움직임 이내에 나올 수 있는 가장 큰 블럭을 출력하는 문제이다. 하나의 상태에서 가능한 움직임은 4방향이고 N*N의 모든 블럭이 움직여야 하므로 하나의 상태에서 4방향으로 움직일 때 연산 횟수는 4*N*N이다. 5번 움직일 때 나올 수 있는 모든 횟수는 4^5이므로 모든 경우를 전부 구했을 때 시간 복잡도는 (1024*N^2*4)이므로 완전 탐색으로 해결 가능하다. 이 때 주의해야 할 점은 한번의 움직임에서 이미 합쳐진 블럭은 다시 안합쳐지므로 visited배열을 관리해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950.. 더보기
BOJ)9202 Boggle 문제: icpc.me/9202 점수를 얻을 수 있는 문자열 셋이 주어진 뒤 Boggle 보드가 주어질 때 주어진 Boggle 보드에서 얻을 수 있는 최고점수 가장 긴 문자열 찾은 단어의 수를 출력하는 문제이다. 단어 사전에 단어가 30만개 까지 들어올 수 있으므로 트라이를 이용하여 해결하면 쿼리를 매번 최대 단어의 길이안에 처리해줄 수 있다. 우리는 단어 사전의 모든 단어들을 Trie에 저장해 준 후 Boggle 보드에서 Bruteforce를 통하여 모든 경우를 탐색하여 나올 수 있는 문자열들을 set에 저장해 준 뒤 답을 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505.. 더보기

티스토리툴바