작심 24/7

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 일단 Core 중에서도 가장자리에 있는 것들은 전선을 연결하지 않기 때문에 고려해줄 이유가 없으므로 코어의 목록에서 제외하고 시작한다. 최대한 많은 Core에 전원을 연결해야 하기 때문에 코어의 개수를 M개라 칭하면, M개 중 M개를 뽑는 조합부터 시작하여 M - 1, M - 2, ... , 0개를 뽑는 경우까지 차근차근 생각해주어야 한다. M개 중 R개를 뽑는 조합을 구하면, 즉 R개의 Core를 사용할 때, 전선 길이의 합이 최소가 되는 경우를 구해야 한다. DFS를 사용하여 상, 하, 좌, 우 방향으로 전선을 만들 수 있는지 판단한다. → 만들 수 있는 경우..

17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 궁수 3명을 배치시키는 경우는 M개 중 3개를 순서 상관없이 뽑는 조합으로 구하면 된다. 궁수가 (5, 2)에 있을 때 공격할 수 있는 위치에 따른 거리들을 표시해 보았다. 궁수가 공격할 수 있는 거리는 궁수 위치에서부터 좌, 상, 우 방향으로 BFS 했을 때의 깊이와 같다는 것을 알 수 있다. 공격할 수 있는 적은 거리가 D 이하인 적 중에서 가장 가까운 적이고 그런 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격해야 하므로 깊이 1부터 탐색해야 하고 방향은 왼쪽, 위쪽..

17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 두 선거구로 나눌 때 각 선거구 안에 있는 영역들은 모두 연결되어 있는 상태여야 한다. 그러므로 두 선거구로 나눌 수 없는 경우는 연결되어 있는 그룹이 세 개 이상일 때이므로 이 경우를 가려주기 위해 먼저 BFS로 연결된 그룹이 몇 개인지 세어준다. 3개 이상일 경우 -> -1 출력 2개일 경우 -> 두 그룹이 각각 선거구이므로 이때 인구의 차 출력 1개일 경우 -> 모두 연결된 상태이므로 다음 단계 넘어감 두 선거구로 나누는 방법은 N개 중에서 K개를 순서 상관없이 뽑는 조합으로 구..

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 모양별로 나올 수 있는 모든 경우를 그려보고 중복되는 부분만 연산으로 저장해두려다 이렇게 푸는 게 아닌 거 같아서 검색해보니 이 4가지 도형을 회전, 대칭시킨 모든 경우가 DFS로 깊이 4만큼 탐색하는 경우와 같다는 것을 알게 되었다. (개소름) 나머지 도형 하나는 중앙 칸을 기준으로 하좌우, 상좌우, 상하우, 상하좌 로 뻗어있는 모양을 가질 수 있고 이 4가지의 경우의 수는 상하좌우를 순서 상관없이 3가지를 뽑은 경우이므로 조합으로 구해주면 된다. #inclu..

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net BFS, 완전 탐색 문제이다. 무조건 3개의 벽을 세워야 하므로 빈칸 n개 중 3개를 순서 상관없이 고르는 조합으로 구현하고 큐로 구현한 BFS로 바이러스의 개수를 구한 뒤 안전 영역의 개수 = 빈칸 개수 - 바이러스의 개수 - 3 의 최댓값을 출력해주면 된다. #include #include #include #include using namespace std; int N, M, cnt, res, x, y, tmp; int arr[8][8], dx[4] ..

1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 조합을 이용해서 푸는 완전 탐색 문제이다. 조합의 경우의 수를 줄이려고 입력받을 때 a, c, i, n, t를 제외시키고 중복되는 단어들도 제외시키고 배울 수 있는 단어들을 따로 만들어놓고 비교하니 시간 초과가 나왔었다. 이렇게 제외시켜서 하는 과정이 그냥 전부 비교하는 방법보다 더 오래 걸린다는 것이다. 그래서 갈아엎고 다시 짰다. 각 단어는 "a, c, i, n, t"를 무조건 포함하므로 K가 5 미만일 때는 어떤 단어도 읽을 수 없기 때문에 0을 출..

11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 파스칼의 삼각형에서 도출해낼 수 있는 이항 계수의 공식은 이다. 그런데 이대로 구현하면 nCr=nCn-r 이라는 성질 때문에 예를 들면 5C1 5C2를 구했는데 같은 값인 5C4, 5C3도 구하게 되는 불필요한 계산을 하게 된다. 그래서 삼각형을 반으로 나누어 중복되는 값을 없애보았다. 이렇게 반으로 나누면 짝수일 때 마지막 숫자만 이렇게 되고 나머지는 이 공식이 똑같이 적용된다. 이대로 구현해주면 끝 #include using namespace std; int main() { int N, K; cin >> N >> K; int dp..

1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net N개의 정수 중에 순서 상관없이 1~N만큼 뽑아 더하는 조합 문제이다. 조합 함수를 만들어서 중간 중간에 원소의 합을 더해주며 그 합과 S를 비교하며 카운트 해주면 된다. #include #include using namespace std; int arr[21] = { 0 }; int cnt = 0, sum = 0, res = 0; vector v; void combination(int N, int S) { if (cnt ==..