다음과 같이 생각할 수 있습니다.
먼저, 앞 배열을 A, 뒷 배열을 B라고 하고, 두 배열의 크기가 모두 N이라고 합니다. 그리고, 두 배열은 모두 오름차순으로 정렬되어 있습니다.
A 배열은 변수 i를 이용하고, B 배열은 변수 j를 사용합니다.
먼저, i=0, j=N-1입니다.
이 때, A[i] + B[j]의 값을 S와 비교해봅니다.
- A[i] + B[j] < S 라면, 두 합은 커져야 합니다. 따라서, i++이 됩니다.
- A[i] + B[j] > S 라면, 두 합은 작아져야 합니다. 따라서, j--이 되어야 합니다.
- A[i] + B[j] == S 라면, 정답을 찾은 것 입니다. 이제 i++을 해서 다른 정답을 찾아봅니다.
cubalys 8년 전
1182번 부분집합의 합 문제는 풀었습니다.
다른 질문글 보니까 배열을 두 배열로 나누어서
각각 경우의 수를 찾은 다음
앞 배열에서 S가 나오는 경우의수 + 뒷 배열에서 S가 나오는 경우의 수 + 앞 뒤 배열에서 S가 나오는 경우의 수 를 구하라고 하시는데
앞 배열 에서 S가 나오는 경우의 수와 뒷 배열에서 S가 나오는 경우의 수는 구할 수 있겠는데
앞 뒤 배열의 부분집합을 하나씩 써서 나오는 경우의 수는 어떻게 구해야 하나요?
부분집합이 겹치지 않도록 그 합을 저장해야 할 것 같은데 감이 안오네요
소스는 1182번 부분집합의 합 소스 입니다.