BOJ 11670(초등 수학) 풀이

solved.ac 티어 : 플래 4

www.acmicpc.net/problem/11670

11670번: 초등 수학

 

이문제는 입력에 음수가 있기 때문에 평범한 이분 매칭으로는 안된다. 그렇다고 음수에다가 값을 더하려고 해도 범위가 -10^6 <= a, b <= 10^6이기 때문에 a*b일 때 최소 -1,000,000,000,000과 최대 1,000,000,000,000가 나올 수 있다.

 

이렇기 때문에 값에다가 1,000,000,000,000 만큼 더해주는 것은 안된다 그래서 좌표 압축이라는 방법을 사용했다.

입력을 좌표 압축 한 다음 배열에 넣어 사용했다.

 

근데 이게 좌표 압축이라고 하기보단 그냥 a+b, a-b, a*b를 저장하고 중복되는 값을 제거하고 정렬한 다음 원래 자신의 값의 인덱스를 가지고 한 거라 좌표 압축이라고 하기가 애매하다.

 

이제 좌표 압축을 하기 위해 lower_bound를 구현해주고(파이썬은 따로 구현해야 된다. 근데 딱히 필요는 없다 그냥. index 하면 된다.) 위치 값을 넣어서 해주면 된다.

 

그러면 위치 값은 최대 n*3까지 나올 것이다. 3*n인 이유는 a+b, a-b, a*b가 모두 들어가 있기 때문에 *3을 해줘야 된다.

 

이제 제출하면 정답이다.

 

 

def lower_bound(val):
    start=0
    end=len(p)
    mid=end
    while end-start>0:
        mid=(start+end)//2
        if p[mid]<val:start=mid+1
        else:end=mid
    return end+1
def dfs(x):
    for i in range(len(l[x])):
        y=l[x][i]
        if t[y]:continue
        t[y]=True
        if q[y]==0 or dfs(q[y]):
            q[y]=x
            return True
    return False
a=int(input())
p=[]
o=[]
h=["" for i in range(a)]
for i in range(a):
    b,c=map(int,input().split())
    p.extend([b+c,b-c,b*c])
    o.append([b,c])
p=list(set(p))
p.sort()
l=[[]]
for i in range(a):
    l.append([lower_bound(o[i][0]+o[i][1]),lower_bound(o[i][0]-o[i][1]),\
              lower_bound(o[i][0]*o[i][1])])
q=[0]*8001
t=[0]*8001
cnt=0
for i in range(a):
    t=[False]*8001
    if dfs(i+1):
        cnt+=1
if cnt==a:
    for i in range(a*3):
        if q[i+1]!=0:
            r=o[q[i+1]-1]
            if r[0]+r[1]==p[i]:
                h[q[i+1]-1]=str(r[0])+" + "+str(r[1])+" = "+str(p[i])
            elif r[0]-r[1]==p[i]:
                h[q[i+1]-1]=str(r[0])+" - "+str(r[1])+" = "+str(p[i])
            else:
                h[q[i+1]-1]=str(r[0])+" * "+str(r[1])+" = "+str(p[i])
    for i in range(a):
        print(h[i])
else:
    print("impossible")