삼성전자 코테 풀이(3) - 게리멘더링2

문제 설명

알고리즘 공부를 위해 지난 삼성전자 코딩 테스트 문제였던 “게리멘더링2” 문제를 풀어보았다.

N X N 격자 맵에서, (x,y,d1,d2) 으로 격자맵을 5개의 선거 구로 나누었을 때, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구차이의 최솟값을 구하는 문제이다. 문제의 상세 설명은 아래 사이트를 참조하자.

• https://www.acmicpc.net/problem/17779

풀이 방법

이 문제는 (x,y,d1,d2)값으로 사용될 수 있는 모든 값에 대해 선거구를 계산을 해야하는 Brute Force 문제이다.

어려운 알고리즘을 사용하지 않아서, 비교적 쉬운 문제이나 (x,y,d1,d2)값에 대한 선거구 별 인구수를 계산해야 할 때, 코딩 실수를 하기가 쉬우니 주의해야한다.

선거구 별 인구수를 계산할때, 다양한 방식으로 계산할 수 있는데, 본인은 디버깅이 쉬운방식으로 구현하였다.

(x,y,d1,d2)에 대한 4중 for 문 이후에, 맵을 선거구 1~4의 x,y범위에 따라서 4개의 사각형 영역으로 나누고 각 사각형에서 선거구5영역에 해당하는 영역의 인구수를 세서 제외해준다.

예를 들어, 선거구 1과 선거구 5의 일부가 속한 첫번째 사각형의 모든 인구를 세면서(=sum[0]) 선거구 5의 인구를 세어(=temp) N1에서 빼주면 선거구 1의 인구수를 구할 수 있다.

• 선거구 1의 인구수 = sum[0] - temp

• 사용 언어: C++
• 알고리즘: for 문으로 모든 경우의 수에 대해 계산하는 Brute Force 문제