[백준 / BOJ] 12101 1, 2, 3 더하기 2 (cpp)
문제 출처 : https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 만들려는 숫자 n이 주어졌을때, n을 1,2,3을 이용해서 만들고 n을 만드는 경우의 수의 조합중 k번째를 찾아 출력하는 문제이다. 풀이 이런 유형의 DP를 풀어본적이 있어서 DP라고 착각했지만, n의 최댓값이 11로 작아서 완전탐색으로도 풀리는 문제다. 로직은 간단한데, 재귀를 이용해서 1,2,3으로 숫자 n을 만드는 모든 경우의 수를 저장해놓은다음 정렬 후 출력하면 된다. 주요 소스코드 void getComb(i..
[백준 / BOJ] 17471 게리맨더링
문제 출처 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net N개의 선거구와 각 선거구에 사는 인원수가 주어진다. 선거구는 2개의 선거진영으로 나뉘며, 이때, 각 선거진영 선거진영 별로 모두 연결되어있어야한다. 이때, 선거진영의 인구수 차이를 최소화하는 값을 구하는 문제다. 풀이 비트마스킹을 이용한 완전탐색으로 푼 문제다. 처음엔 비트마스킹 + 백 트래킹으로 생각했으나, 이 방법으로는 모든 경우를 봐주지 못해서 풀기 힘들어 보였다. 알고리즘은 다음과 같다. 1. ..