어흥

문제 링크: https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름�� www.acmicpc.net 1. 주의할 점 - 각 구역을 어떤 방식으로 나눌건지 잘 계산한다 - 브루트포스를 통해 경우의 수 전부 구해본다 2. 구현 - 각 인구를 입력 받으면서 배열에서의 총합을 따로 구한다 - D1, D2의 최소 길이가 1인 것을 감안하여 DFS를 수행한다 - DFS를 수행하며 각 변이 범위밖으로 넘어가지 않는다면 브루트포스 함수인 Start()를 수행한다 - 1~4 구역까지 인구수 전부 구한..

문제 링크: https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 1. 주의할 점 - 한팀에는 최소 1명이 있을 수 있고, A팀과 B팀의 인원수는 같지 않아도 된다 - 현재 구현한 방법은 중복된 경우가 있기 때문에(X2) 시간이 2배로 든다 2. 구현 - 브루트포스를 통해 1명~N-1까지 팀을 이뤘을때 각 팀원들에 해당하는 능력치의 합을 구한다 - 브루트포스의 경우, Next_permutation 함수를 ..

문제 링크: https://www.acmicpc.net/problem/2549 2549번: 루빅의 사각형 첫 번째 줄에는 움직이는 횟수를, 두 번째 줄부터는 한 줄에 하나씩 타일을 움직이는 방법을 순서대로 출력한다. 이때, 격자판의 i번째 행을 k칸 움직였다면 정수 1과 i와 k를 빈칸을 사이에 두고 www.acmicpc.net 1. 주의할 점 - 푸는 방법이 여러가지 존재하지만, 여기서는 백트레킹을 활용해서 해결한다 - 한 열/행을 1~3칸 이동하는것은 전부 1번 옮긴것과 같다 2. 구현 - 현재 배열의 상태(Arr[][])와 최종적으로 원하는 배열의 상태(Corr[][])를 비교하여 틀린 개수를 반환하는 Cal() 함수를 구현한다 - Cal() 함수를 통해 다른 개수를 반환 받은 후, 다음과 같은 가..

문제 링크: https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 1. 주의할 점 - 이분탐색 + BFS를 사용하여 해결한다 - Left와 Right값을 잘 설정한다 - 모든 정점이 연결되어 있다는 보장은 없다 2. 구현 - 모든 간선의 정보를 V[] 벡터에 넣고 이분탐색을 통해 Mid값으로 Start부터 Dest까지 건널 수 있는지 확인한다 - 건널 수 있다면 더 많은 값으로도 가능한지, 건널 수 없다면 더..

문제 링크: https://www.acmicpc.net/problem/11085 11085번: 군사 이동 문제 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재�� www.acmicpc.net 1. 주의할 점 - 가중치가 큰 간선들부터 연결을 한다 - 크루스칼 알고리즘을 사용한다. 단, 종료조건이 다르다 2. 구현 - 입력 받는 간선에 대한 정보를 우선순위큐에 저장하며, 가중치의 내림차순으로 정렬한다 - 우선순위큐에서 간선에 대한 정보를 1개씩 빼면서 만약 2개의 도시가 이어져 있지 않다면 연결하고, Result에 해..

문제 링크: https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 node >> edge; for(int i=1;i s >> e >> val; arr[s][e] = val; } for (int k = 1; k

문제 링크: https://www.acmicpc.net/problem/3709 3709번: 레이저빔은 어디로 문제 레이저박스라는 게임은 정사각형 모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 �� www.acmicpc.net 1. 주의할 점 - X,Y의 입력으로 받거나 Y,X 입력으로 받거나 둘중 하나로 통일해야 한다 2. 구현 - Num, Mirror의 수를 입력 받은 후, Arr[][]배열을 항상 0으로 초기화한다 - 우향우 거울인 경우, Arr[][] 배열값을 1로 설정한다 - 어떤 지점에서 레이저가 시작되는지에 따라 4가지의 초기값이 다른 DFS를 수행한다 - DFS()를 통해 범위 밖으로 나가..

문제 링크: https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 1. 주의할 점 - 모든 변수를 Long Long으로 받아들인다 2. 구현 - 면접장으로 가는것이 아닌 면접장에서 출발하도록 그래프의 방향을 바꿔서 넣는다 - 면접장을 우선순위큐에 넣고 다익스트라 알고리즘을 통해 각 도시까지의 거리를 구한다 - For문을 수행하며 1부터 Node 번호까지 비교하여 Maxi, Result을 갱신한다..