브루트포스
-
백준 1941 소문난 칠공주Algorithm/BOJ 2021. 6. 6. 16:50
출처: https://www.acmicpc.net/problem/1941 분류: brute force 접근방식 처음엔 그냥 bfs, dfs로 풀 수 있겠거니 했으나.... 점점 어라? 어라..? 어라....????!! 하며 쉽지 않았던 문제였습니다. 중복을 어떻게 줄여줘야할지 도통 감이 오질 않더라구요.. 결국은 다음와 같은 과정으로 해결했습니다. 1. 각 칸을 0~24로 두고, 0~24 중 7개를 선택하는 조합을 구한다. (약 48만개) 2. 조합에서 S가 4명 이상인지 확인한다 3. 조합이 모두 인접해있는지 확인한다. 1, 2번까지는 어렵지 않게 구할 수 있을 거 같은데 3번이 살짝 까다롭네요. 3번은 만든 조합의 0번부터 시작해 인접한 수가 조합안에 있는지 확인하고 queue에 담아주면서 탐색하는 ..
-
백준 10819 차이를 최대로Algorithm/BOJ 2021. 3. 16. 13:20
출처: www.acmicpc.net/problem/10819 분류: 완전탐색, 순열 접근방식 n이 최대 8밖에 되지 않아 가능한 배열 조합을 모두 구해서 주어진 식대로 계수의 최댓값을 계산했습니다. 주어진 예제에서는 [8, 15, 1, 20, 4, 10] 경우에 가장 큰 최댓값이 나오는데 어떤 경우에 최대가 나오는 특별한 규칙이 있는건지는 잘 모르겠습니다.. ㅠㅠ 순열을 오랜만에 해서 처음에는 배열을 만들어가고 해당 수를 넣었는지 체크하는 bool 배열을 만들고... 굉장히 비효율적으로 풀었었네요 ㅠㅠ 덕분에 오랜만에 순열을 다시 복습해볼 수 있어서 좋았네요 :) 전통적인 순열은 스왑을 통해 백트래킹 방식으로 구할 수 있습니다. 앞에서부터 해당 자리에 들어갈 수를 채워넣어가는 방식으로 바꿀 자리의 인덱스..