목록Algorithms/Brute Force (4)
혼종 꼬지마루
https://www.acmicpc.net/problem/18192 음... 정~~~~말 오랜만에 문제를 풀려고 앉았는데.... 재밌는 문제라해서 들어가 봤더니 이런 세상에?? 마치 B형 시험과 같이, 주어지는 header나 cpp파일을 include 해야 되는 문제.... 문제도 뭔가 되게 긴장되게 생겼지만, 문제가 B형에 비해서 상당히 허술하다.... 비교를 하자면, B형은 내가 생각할 때 크게 두가지로 나뉘는 것 같다.1. 충실히 구현만 하면 풀 수 있다. 하지만,,,, 최적화 부분에서 score가 메겨지는 유형2. 구현이 거지같이 힘들거나 어려운 문제 그러나 이 문제는 그냥.... 허술하기 짝이 없다;; 주어지는 조건이라고는 함수 호출 2500번이 끝.... 한마디로 주어지는 최적화 답과는 달라도..
전형적인 Brute Force 문제이다. 색종이를 큰사이즈부터 가능한 위치에 붙여넣고, 모두 붙였다면 최소값을 찾는 문제 원래 나는 stl을 안쓰고 문제를 푸는것을 선호하지만, 이 문제는 안쓰고는 시간초과가 날 것 같아서 vector를 사용했다 1. map을 순회하며 색종이를 붙일 수 있는 위치를 찾는다. 2. 큰사이즈(5x5) 부터 작은 사이즈(1x1)를 차례대로 붙이면서 다음으로 넘어간다. 3. 만약 더이상 붙일 자리가 없다면 최소값을 갱신 4. 붙이는 갯수가 답보다 커진다면 return 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include ..
간만에 원큐에 푼 문제라 기분이 너무 좋다... 그냥 재귀로 싹다 돌려줘도 되는 문제 물론 전체 포지션을 다 고려한다고 했을 경우에는 O(11^11)이라 밥먹고 오면 풀릴 시간이지만 문제 조건이 '한명당 적합한 포지션은 최대 5개'라는 조건이 붙어 있어서 O(5^11) 까지 줄어드는 문제 1234567891011121314151617181920212223242526272829303132333435363738394041#include #define SIZE 13using namespace std; int S[SIZE][SIZE];bool check[SIZE];int C, dab; void dfs(int d, int sum){ if (d == 11) { dab = dab > sum ? dab : sum; r..
처음에 버릴 수 있는 부분이 있는걸 모르고 헤맸습니다... 말그대로 브루트 포스!! 1. 1~10000길이만큼 잘라서 얻을 수 있는 각각의 나무의 값을 tmp배열에 저장 2. 내림차순 정렬 3. 앞에서 부터 더하며 이전까지 더한 것이 지금값과 더했을때 보다 크다면 break 4. 최대값과 비교하여 갱신 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 #include #include #define MX 1002 using namespace std; int arr[MX]; int N, C, W, dab, lim = 987654321; bo..