겜돌이의 개발일지

문제 백준 13913 숨바꼭질 4 C++ 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 숨바꼭질에서 경로를 저장하는 배열 vector만 추가해주면 될 줄 알았더니 메모리 초과가 떴습니다. 곰곰히 생각해보니 방문하는 모든 지점을 각각의 queue에 저장하는 것이 문제였습니다. 따라서 가장 처음 해당 지점을 방문할 때, 어디서 방문했는지 저장하는 배열을 선언하여 최단 경로만을 저장하는 방식으로 해결하였습니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 ..

문제 백준 17471 게리맨더링 C++ 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 N까지의 노드를 0과 1로 양분합니다. 0과 1을 양분할 수 있는 모든 경우의 수에 대해 실행합니다. (조합 이용) 0과 1로 양분할 수 있게 영역이 결정되면, 각 영역을 서로 0은 0끼리, 1은 1끼리 연결할 수 있는지 확인힙니다. 연결이 가능하다면, 각각의 합을 구한 후 차를 구하고, 최솟값과 비교하여 갱신합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..

문제 백준 5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 현재 위치와 이동 횟수를 저장하는 queue를 선언합니다. 위로 올라갈 수 있을 때, 아래로 내려갈 수 있을 때 queue에 push 해주며 bfs를 실행합니다. 현재 위치가 G와 같다면 이동 횟수를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include..