[알고리즘 문제 풀이][좌표압축] 백준 13135번 - Corrupt Election

백준 13135번 Corrupt Election 문제입니다.

(값/좌표 압축 학습용 문제)

 

 

- 문제 설명: https://www.acmicpc.net/problem/13135

- 문제 풀이:

 

본 문제에서 가장 먼저 중요했던 것은, 문제에서는 무효표를 처리한 기준을 묻고 있지만 실제로 무효표 기준으로 따지게 되면 문제 풀이가 복잡하다는 것입니다. 무효표 기준이 "한 후보에게 X표 이상을 투표했거나 총 Y 표 이상 투표한 유권자들의 표를 무효표 처리한다." 이기 때문입니다.

 

본 문제의 풀이는 아래 출처의 해설을 참고하였습니다. 

무효표 대신 유효표 기준으로 전환하게 되면 (무효표를 거르는 것과, 유효표를 선택하는 것은 결국 결과가 같습니다!), 한 후보에게 투표한 것이 무조건 X 아래이고, 총 투표도 무조건 Y 아래인 사람을 유효표로 선택하면 됩니다. 그러면 범위를 찾는 것이 훨씬 쉬워집니다.

https://gooddaytocode.blogspot.com/2016/08/blog-post_6.html

 

그리고 본 문제는 좌표 압축 문제인데, 좌표 압축이라고 해서 뭔가 엄청난 압축 기법이 필요한 것은 아니었습니다. 문제에서 다루는 전체 좌표의 범위가 100,000 x  100,000 으로 굉장히 큽니다. 심지어 유효표 기준을 세우기 위해 (max (A, B), A + B) 를 한다면 100,000 x 200,000 이 될 것입니다. 메모리 제한 (64 MB) 이 있으므로 이렇게 큰 배열은 잡을 수가 없게 됩니다. 그래서 본 문제를 풀기 위해서는 입력으로 들어오는 1000개의 표 정보들만 가지고 x, y 좌표로 표현하면 됩니다. (=> 이것이 바로 좌표 압축!)

 

1000 개의 표 정보만 가지고 (max(A, B), A+B) 로 배열을 만듭니다. (유효표를 선택했을 때 해당 후보가 당선이 되어야하기 때문에 저는 이 때 나중에 이를 계산하기 위한 A-B 값도 추가해주었습니다.)

또한 max(A, B) 와 A+B 배열도 각각 만들어주었습니다.

 

그리고 나서 이렇게 만들어진 값을 정렬해줍니다. 가능한 x 값 (max(A, B)) 들도 정렬을 해주고, 가능한 y 값 (A+B) 들도 정렬을 해줍니다.

 

그런 후에 가능한 x 와 가능한 y를 이중 포문을 돌면서 이 기준으로 유효표를 선택하면 해당 후보가 당선이 되는 것이 맞는지 (= 유효표들을 고르면 A가 당선되어야하므로, A-B 들의 합이 양수가 맞는지) 체크만 해주면 됩니다.

 

A-B 들의 합이 양수가 맞는지를 체크하면 되는데, 이걸 또다시 주민들마다 일일히 확인하면 시간이 너무 오래걸리기 때문에 저는 이중 포문을 돌기 직전에 주민들 표를 돌면서 A-B 의 합을 미리 D라는 배열에 채워두었습니다.

 

이렇게 준비가 되었으면 이중 포문을 돌면서 "x (max(A, B) 와 y (A+B) 기준에 해당하는 A-B 합 + 그것보다 더 낮은 기준일 때 유효한 표도 다 더해줌" 이 총합이 양수인지 확인하였습니다.

예를 들어, 한 기준이 전체 제출한 표의 합의 3개 아래라면, "3개인 경우 + 2개, 1개" 가 다 합해져야할 것입니다. 그래서 이중 포문을 돌면서 1, 2, 3 ... 순으로 누적해가며 표의 특정 기준일 때의 A-B 합을 최종적으로 구해가는 것입니다.

 

- 코드: 

 

N = int(input())
people = []
ans = 0
x = {0, 100000} # for range
y = {0, 100000}
xind = [0] * 100010
yind = [0] * 100010

for _ in range(N):
    coor = list(map(int, input().split()))
    people.append([max(coor), sum(coor), coor[0] - coor[1]])

    x.add(max(coor))
    y.add(sum(coor))

xc = sorted(list(x))
yc = sorted(list(y))

D = [[0] * len(yc) for _ in range(len(xc))]

for i, v in enumerate(xc):
    xind[v] = i
for j, v in enumerate(yc):
    yind[v] = j

for p in people:
    D[xind[p[0]]][yind[p[1]]] = p[2]

xc_len = len(xc)
yc_len = len(yc)

for i in range(xc_len):
    for j in range(yc_len):
        if i > 0 and j > 0 and i < xc_len-1 and j < yc_len-1:
            D[i][j] += D[i-1][j] + D[i][j-1] - D[i-1][j-1]
            if D[i][j] > 0:
                ans += (xc[i+1]-xc[i]) * (yc[j+1] - yc[j])    
    
print(ans)

xind 는 xc, yc 에 속하는 값 중 하나가 주어졌을 때 xc와 yc 의 인덱스 중 어디인지 바로 찾아가기 위해서 만들었습니다.