[ baekjoon ] 두 배열의 합 2143번 ( python )

문제

백준 2143 두 배열의 합 풀이 ( 파이썬 )

www.acmicpc.net/problem/2143

2143번: 두 배열의 합

 

풀이

부분합을 담아 놓고 배열 하나는 오름차순 정렬 하나는 내림차순 정렬로 바꾸어 합이 t 보다 작을 때는 오름차순 한 리스트의 인덱스를 1 증가시키고 합이 t보다 클 때는 내림차순 한 리스트의 인덱스를 1 증가시킨다.

만약 합이 t와 같다면 바로 answer를 1 증가 시키지 않고 각 리스트에 같은 값이 있는지 검사해줘야 한다.

t=int(input())
n=int(input())
a=list(map(int,input().split()))
m=int(input())
b=list(map(int,input().split()))

lenA=len(a)
lenB=len(b)

for i in range(lenA):
    add=a[i]
    for j in range(i+1,lenA):
        add+=(a[j])
        a.append(add)

for i in range(lenB):
    add=b[i]
    for j in range(i+1,lenB):
        add+=(b[j])
        b.append(add)

a.sort()
b.sort(reverse=True)

indexA=0
indexB=0
answer=0
lenA=len(a)
lenB=len(b)

while (indexA<lenA and indexB<lenB):
    # 합이 t와 같을 때
    if (a[indexA]+b[indexB])==t:
        cntA=0
        cntB=0
        subsumA=a[indexA]
        subsumB=b[indexB]
        # 합이 같을 때 각 리스트에 같은 값이 있는지 확인
        while indexA<lenA:
            if subsumA == a[indexA]:
                cntA+=1
                indexA+=1 
            else:
                break
        while indexB<lenB:
            if subsumB == b[indexB]:
                
                cntB+=1
                indexB+=1
            else:
                break
        answer+=(cntA*cntB)
    # 합이 t보다 작을 때
    elif (a[indexA]+b[indexB])<t:
        indexA+=1
    # 합이 t보다 클 때
    else:
        indexB+=1
print(answer)