나의 공부장

문제 링크 : https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름�� www.acmicpc.net 문제 풀이 처음에는 문제가 간단하면서도 복잡하다는 생각이 들어서, 예제를 따라 그리다 보니까 문제가 이해가 됐습니다. (문제 이해가 빠르면 더 시간을 단축할 수도!) 가장 중요한 것은 (x, y, d1, d2)를 정하는 것입니다. 정하고 나서 제5구역을 미리 먼저 만들고, 나머지 1 ~ 4 구역을 문제에서 제시한 범위에 따라 그려줍니다. 다 그려줬다면, 각 구역에 따라 합을 계산해서 ..

위의 세 가지 모두 경우의 수를 다 돌려보는 느낌이 들지만, 정확히 따지자면 다음과 같다고 합니다. 백트래킹 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법입니다. 반드시 DFS만으로 가능한 게 아니고 BFS 등으로도 가능하지만 일반적으로는 DFS와 연관이 깊다고 합니다. 브루트 포스 꼭 '깊이'나 '탐색'의 개념이 아니더라도, 모든 경우의 수를 다 대입해보는 기법입니다. DFS 여러 지점을 한 단계씩 거쳐가면서 탐색하고, 스택의 개념을 이용해서 이전 단계로 돌아가야만 DFS라고 합니다.

문제 링크: https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 문제 풀이 문제가 쉬운 거 같았지만, 예제 마지막 테케를 보고 살짝 꼬여있다는 것을 알았습니다. 서로 연합이 되려면 나의 국가와 다른 국가의 차이가 L 이상 R이하가 되어야 서로 연합이 될 수 있습니다. 문제를 잘게 쪼개서 순서를 세우면 다음과 같습니다. 1. 입력을 받습니다. 2. 인구 이동이 가능한지 mark로 표시합니다. (백준 문제에서 단지 번호 붙이기 266..

문제 링크: https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net 문제 풀이 카드의 합이 M을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만들면 됩니다. 카드가 1 ~ N장이 있을 때,..

문제 링크: https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 예를 들어 {1, 2}의 부분 수열은 다음과 같다. 공집합, {1} , {2} , {1, 2} = 4개(2^2) 이러한 부분 수열들을 다 만들려면, 해당 숫자를 포함을 시킬지 안 할지를 결정해서 더 해주면 된다. 주의할 점이, 공집합은 0이랑 결과값이 같기 때문에 만약에 s가 0이라면 -1을 해줘야 한다. 이는 모든 수열에서 해당 숫자를 ..

문제 링크: https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 풀이 N X M 판에서, 8 X 8 판을 떼어내서 체스판이 되게 다시 칠해주는 작업을 할 때 그 횟수가 최소가 되는 부분을 찾아내는 문제입니다. 문제를 잘게 쪼개서 보면 다음과 같이 정리할 수 있습니다. 1. N X M을 8 X 8의 크기로 잘라낸다. (수많은 체스판들이 나옵니다.) 2. 잘라난 체스판을 가장 왼쪽 위가 흰색인 부분과, 가장 왼쪽 위가 검정색인 부분을 나눈..

문제 링크: https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 풀이 9명의 난쟁이 중에서 2명이 공주에게 거짓말하고 있습니다. 2명을 찾는 방법은 9명의 난쟁이들의 키를 모두 더한 값에서 2명씩 빼면서 그 결과가 100이 되는 경우를 찾으면 됩니다. [9명의 난쟁이들의 키의 합] - [거짓 난쟁이 후보 1] - [거짓 난쟁이 후보 2] = 100 소스 코드 #include #include #include using namespace std; int ..

문제 링크: https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 문제 삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다. [그림] 자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다. Tn = 1 + 2 + 3 + ... + n = n(n+1)/2 1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어, 4 = T1 + T2 5 = T1 + T1 + T2 6 = T2 + T2 or 6 = T www.acmicpc.net 문제 풀이 n의 크기가 1000밖에 되지 않기 때문에 모든 경우를 다 확인해보면 됩니다. 구하기에 앞서서, 50까지의..