https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 비트마스킹을 사용해서 풀었다. 재귀로 풀어도 상관없다. 비트마스킹을 통해서 팀 A와 B를 구분해주었다. i번째 비트가 1으로 켜져있다면 i번째 사람은 A팀에 들어간 것이고 i번째 비트가 0으로 꺼져있다면 i번째 사람이 B팀에 들어간 것이다. 사람 20명으로 만들어 낼 수 있는 모든 경우에 대해서, O(N^2) 로 두 사람을 골라낸 다음 그 두 사람이 같..

https://www.acmicpc.net/problem/1174 1174번: 줄어드는 수 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는 www.acmicpc.net 브루트포스 문제. 줄어 드는 수 중 가장 큰 수는 9876543210 이므로, 0부터 숫자를 1씩 증가하면서 "줄어드는 수" 인지 체크하는 방법은 TLE를 받게 된다. [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 순으로 배열된 배열에서 각각의 숫자를 포함하거나 포함하지 않는 경우를 기준으로 브루트포싱을 해주면 순회 횟수가 2^10 밖에 되지 않으므로 무난하게 해결할 수 있..

https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 신맛과 쓴맛이 최대한 비슷해지게 만드는 문제. N이 10으로 매우 작아서 O(2^N) 시간복잡도를 가지는 브루트포스로도 문제를 해결할 수 있다. 해당 문제의 구현 방법으로는 재귀함수를 사용한 구현과(dfs-like) 비트마스킹을 이용한 구현이 있는데, 비트마스킹을 연습하기에 나쁘지 않은 유형이지 싶어서 비트마스킹으로 풀어보았다. i번 재료를 섞는 경우에 i번 비트를 1로 켜고..

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

www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 처음 보고 든 생각은 "R과 C의 범위가 작으니까 DFS등으로도 해결할 수 있을 거 같다" 였다. 구현 방법은 뭐 여러가지가 있겠지만, 나는 비트마스킹을 연습할 겸 비트마스킹으로 해결해 보기로 했다. 우선 들어오는 문자들에서 'A'만큼을 빼서 0부터 시작하는 숫자로 만들어준다음 각각 0 번째 비트, 1번째 비트, .... 등으로 각각의 비트에 방문여부를 기록해준다. 더보기 #include using na..