백준 2143번 두 배열의 합

< 백준 2143번 두 배열의 합 - 마포 코딩박 >

사용한 알고리즘: map


 임의의 수 T 와 두 배열 A, B 가 주어졌을 때 A 와 B 의 부배열의 합으로 T 를 만들 수 있는 경우의 수를 구하는 문제였습니다.

 풀이는 다음과 같습니다.
(1) (코드 17~24)
 A 의 모든 부배열로 만들 수 있는 값을 map에 저장합니다.
 예를들어 A[1]~A[3] , A[2]~A[7] 의 두 부배열이 10 이라는 값을 만들면 map[10]=2 입니다.

(2) (코드 25~33)
 T - ( B 의 모든 부배열로 만들 수 있는 값 ) 의 모든 경우를 보며, 이 값을 만들 수 있는 A의 부배열의 개수 ( 과정 (1) 에서 구해놓음 ) 가 답이 됩니다.