오딩이

출처 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 🔍 Solve 조합을 이용한 완전 탐색이며, dfs를 사용했습니다. 다음과 같은 순서로 구현했습니다. 1. 그래프(배열) 만들기 - 조합 2. 선거구 연결 - 그래프 탐색(dfs) 3. 인구수 파악 부분집합이 아닌 조합을 사용한 이유는, 배열 1이 뽑혔으면 배열 2는 배열 1의 여집합이기 때문에 부분 조합을 사용하면 중복되는 배열이 반환됩니다. 따라서 1부터 N/2까지의 개수를 뽑는 조합을 사용했습니다. 조합..

출처 : https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 🔍 Solve 문제 그대로 따라 하는 시뮬레이션 문제입니다. 해당 문제는 방향을 전환하는 문제이므로, 방향 배열을 순서를 지켜서 만들어야 합니다. 저는 동->남->서->북 순서로 시계방향으로 돌아가는 순서로 만들었습니다. 방향을 전환할 때 L(왼쪽으로 90도)라면 방향 배열의 인덱스를 -1해주고, D(오른쪽으로 90도)라면 방향배열의 인덱스를 +1 해주었습니다. (0~4의 범위를 벗어날 때 예외..

출처 : https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 🔍Solve 순조부의 전형적인 순열 문제입니다. 순열은 서로 다른 n개 중 r개를 택하며, 순서를 고려합니다. 주의해야 할 점은 n이 12를 넘어가면서(12!) 시간 복잡도가 폭발적으로 증가합니다. 해당 문제는 n이 8까지이므로, 무리없이 돌릴 수 있었습니다. 운동 키트의 증량 증가량을 담은 배열을 선언하고 해당 배열을 순열 함수를 돌립니다. permutation의 매개변수는 ..

출처 : https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 🔍 Solve BFS를 사용하여 풀었습니다. 문제에서 주의해야 할 점은 공기와 접촉된 치즈는 한 시간이 지나면 녹아 없어지지만, 치즈 안에 있는 구멍에 인접한 치즈는 녹지 않는다는 점이었습니다. 따라서 치즈가 아닌, 공기의 위치를 BFS로 탐색하여 치즈를 녹이는 방법을 선택했습니다. 치즈가 모두 녹기까지 시간이 얼마나 걸렸는지를 배열에 저장하기 위해 기존 공기가 0, 치즈가 1의 값을 가졌던 것을..