문제 정보

• 플랫폼: 백준
• 문제 번호: 2143
• 문제 이름: 두 배열의 합
• 문제 링크: https://www.acmicpc.net/problem/2143
• 난이도: 골드 3

풀이 방법

간단히 어떤 방식으로 풀었는지 설명해주세요.

예시:
- 알고리즘: DFS/BFS, DP, 그리디 등
- 시간 복잡도: O(n)
- 공간 복잡도: O(n)

• 처음에 생각한 방식은 A의 부배열과 B의 부배열의 조합에 대해서 일일이 계산하는 방식의 완전 탐색을 생각했었습니다.
• 하지만 해당 방식은 조합의 수가 다양해 보여, 관점을 A의 부배열과 B의 부배열이 각각 만들 수 있는 수로 집중하게 되었습니다.
• 그래서 A와 B에 대해 긴 배열을 생성해서 index는 만든 부배열의 합, value는 해당 idx를 만들 수 있는 경우의 수를 계산하는 방식을 떠올렸습니다.
• 하지만 해당 문제의 경우, 목표 값인 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 정도이기 때문에 긴 배열을 사용하면 OOM이 발생하기에 list 대신 Map<Integer, Integer> 기반으로 저장하는 방식을 사용했습니다.
• 이렇게 계산한 A_map과 B_map에 대해서, A_map의 keySet을 가져온 다음 순회하면서, 해당 key에 대응되는 B_map.containsKey(T - a_key) 가 true일 경우 A_map.get(a_key) * B_map.get(T - a_key)를 최종 결과에 더하여 문제를 마무리 했습니다.
• 이 경우, A와 B의 부분 배열을 전체 계산하는 과정에서, 다음과 같은 수식으로 O(N^2)으로 봤기에 충분히 가능하다고 생각하여 해당 방식으로 해결하게 되었습니다.

$$\text{개수} = \frac{n(n-1)}{2} + n = \frac{n(n+1)}{2}$$

• 여기에 n = 1000을 대입해보면 다음과 같이 결과가 나와 1억번 연산 내에 충분히 계산이 가능합니다.

$$\frac{1000 \times (1000 + 1)}{2} = \frac{1000 \times 1001}{2}$$$$= 500 \times 1001 = 500,500$$

체크리스트

• 코드가 정상적으로 실행되나요?
• 커밋 메시지가 컨벤션을 따르나요?
• 파일명이 올바른가요? ({닉네임}.{확장자})

추가 코멘트

(선택사항) 추가로 공유하고 싶은 내용이 있다면 작성해주세요.