https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 그래프이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 조합론, 깊이 우선 탐색 설명 위와 같이, 하나의 시를 2개의 선거구로 나누려 합니다. 선거구의 각 구역은 모두 직/간접적으로 이어져 있어야 하며,이때 두 선거구 간의 인원 수의 차이가 최소가 되어야 합니다. n이 2 !selected[index] }.sum() // 선거구2 인구 수 answer = minOf(ans..

https://www.acmicpc.net/problem/15439 15439번: 베라의 패션 베라는 상의 N 벌과 하의 N 벌이 있다. i 번째 상의와 i 번째 하의는 모두 색상 i를 가진다. N 개의 색상은 모두 서로 다르다. 상의와 하의가 서로 다른 색상인 조합은 총 몇 가지일까? www.acmicpc.net 난이도 : 브론즈 4 태그 : 수학, 구현, 조합론 설명 단순히 n * (n-1)로 구할 수 있을 것 같습니다. 소스코드 fun main() = println(readln().toInt().let { it * (it - 1) }) 후기 최근 숏코딩에 맛들려 브론즈 문제들의 경우 요상한 코드를 쏟아내고 있습니다. 현업에서 이러면 짤릴 것 같으니, 백준에서라도 해봐야겠습니다.

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 난이도 : 실버 5 태그 : 수학, 다이나믹 프로그래밍, 조합론 설명 서쪽과 동쪽의 다리를 서로 잇는 문제입니다. 항상 양쪽 다리 개수가 같거나, 강 동쪽이 다리가 더 많으므로, 단순히 오른쪽 다리 m개 중 왼쪽다리 개수 n만큼을 고르는 조합으로 볼 수 있습니다. 즉, mCn 으로 볼 수 있겠네요. 소스코드 fun main() = with(System.`in`.bufferedReader()) { ..

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 난이도 : 골드 3 태그 : 수학, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 조합론, 백트래킹 설명 DFS를 사용해 풀면 되겠네! 라는 생각이 바로 떠올랐지만, 생각해보니 순수 DFS만으로 풀기에는 조금 무리가 있었습니다. 결국... 이게 뭐지??? 하는 생각에 태그를 펼쳐봤습니다. 그렇습니다. 이 문제는 1. 5 x 5 = 25명의 자리 중 7명을 뽑고(..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 난이도 : 실버 2 태그 : 수학, 조합론, 백트래킹, 재귀 설명 주어진 숫자 중 6개를 만드는 모든 조합을 찾는 문제입니다. 숫자 자체가 오름차순으로 주어지니, 입력 배열을 정렬할 필요는 없습니다. 저는 백트래킹(재귀)으로 주워진 숫자들의 모든 경우의 수를 체크하였습니다. 소스코드 import java.util.* var n = 0 lateinit var arr: Array latei..

https://www.acmicpc.net/problem/17358 17358번: 복불복으로 지구 멸망 (2,1,4,3), (3,4,1,2), (4,3,2,1) 총 3가지 경우가 가능하다. www.acmicpc.net 난이도 : 실버5 태그 : 수학, 조합론 설명 컵 하나와 다른 컵 하나를 서로 바꿉니다. 컵의 갯수는 항상 짝수이며, 모든 컵은 단 한 번만 바뀌어야 할 때, 가능한 조합의 경우의 수를 구하는 문제입니다. 예시와 함께 보겠습니다. 6개의 컵이 있다 가정을 해보겠습니다. 6개의 컵중 하나를 선택합니다. 위치를 옮길 다른 컵 하나를 선택합니다. 5개의 컵 중 하나를 선택할 수 있으므로, 현재까지 경우의 수는 5입니다. 다른 컵을 하나 선택합니다. 저는 2번컵을 집었습니다. 남은 3개의 컵중 위..