https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 입력으로 들어오는 정수 A를 숫자가 아니라, '0' 부터 '9' 까지의 문자가 들어오는 문자열로 보면 이 문자열 배열에 대해서 next_permutation 을 통해서 순서를 섞어낼 때의 모든 조합을 구할 수 있다. 모든 순서를 찾아보는 시간복잡도는 O(N!) 이고, A는 10^9보다 작은 수이기 때문에 최대 9자리라서 N=9 이다. 이때의 계산 횟수는 대략 40만언저리쯤 ..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 브루트포스 문제이다. 어떠한 위치 i에서 고일수 있는 물의 양은, 그 양쪽으로 i보다 높이가 높은 두개의 블록 l,r 이 있을때, min(l,r) - i 만큼 고일 수 있다. 모든 i에 대해서 순회하는데 O(N), 높이가 최대로 높은 두 블록 l,r 을 찾는데 O(N)으로 전체 시간복잡도는 O(N^2) 이다. 위치 i에서 l,r을 찾고자 할때, l이나 r이 존재하지 않는 경우가 ..

https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net KOI 2019 중등부 1번 브루트포싱 문제였습니다. 단순하게 어떠한 추에 대해서 생각해볼 수 있는 세가지 경우 왼쪽에 놓는다 오른쪽에 놓는다 저울에 올리지 않는다 이 셋을 모두 고려해서 소스코드를 작성해주면 된다 전체 시간복잡도는 O(3^N)인데, N이 13으로 매우 작아서 160만번 정도밖에 계산하지 않는다. 왼쪽에 놓는 경우에 측정 가능한 무게 K (지문에서는 □로 표기) 는 줄어들게 되므..

https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 중량이 500 미만으로 떨어지는 일이 없도록하는 경우의 수를 구하는 문제. 입력으로 들어온 배열의 크기 N이 그렇게 크지 않아서 브루트포스를 통해 모든 경우를 다 생각해봐도 그리 오래 걸리지 않는다. 구현에는 c++의 next_permutation을 사용했다. 정렬된 배열에서 next_permutation을 사용하면 해당 배열을 통해 만들수 있는 모든 경우의 수를 한번씩 순회해 볼 수 ..

https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 풀긴풀었다만 매우불쾌한문제;; N의 범위가 그리 크지 않아서 점 세개를 정하는 경우의 수를 브루트포싱해도 된다. 문제는 점 세개의 좌표를 정해주기 위해서 무려 "6중 포문" 이 필요하다는건데 ㅠㅠ x,y 좌표를 x*N+y로 뭉쳐서 3중포문으로 압축할 수 있다지만 일단 길고 장황하게 구현해봤다. 꽃들이 겹쳤는지 확인하기 위해서 tmp라는 배열에 꽃들을 직접 그려보고, 꽃으로 표시된 부분(1이다) ..

처음 봤을때는 전구를 두번 켜고끄고 할필요가 없다는 내용을 떠올리고 무지성 브루트포싱을 시도했지만 바로 2^100 TLE 나만 모르는 웰논 풀이 윗줄에 대해서 비트마스킹 등으로 브루트포싱을 진행해주면, 그 아랫줄은 윗줄의 상태에 따라서 켜고끄고 여부를 결정할수 있다고 한다. 쭉 순회해가면서 처리하기. 구현자체는 그리 어렵진 않았다. https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net #include using namespace std; ..