서로 다른 정수로 이루어진 배열 A (ex {1,3,4})
정수 B가 주어질때 서로 다른 숫자 3개를 뽑았을 때 합이 B가 되는 가짓수를 구하는 방법
배열 A의 크기는 <= 3000이고 원소와 B의 범위는 <= 300,000입니다
제한 시간은 1초인데 빠르게 구하는 알고리즘이 있을까요?
두 정수로 만들 수 있는 정수를 체크하고 (B-A[i])가 존재하는 지 체크하여서 풀려고했는데
중복되는 원소들이 생겨서 안되더라구요.. 어떤 방법으로 해결해야하나요?
그냥 있는지만 체크하는게 아니라 몇 가지 경우가 있는지를 추가적으로 세어줘야지
예를 들어 1,2,3,4 면 두 수로 5를 만드는 방법이 1+4, 2+3 두 가지가 있는걸 체크해줘야함
그리고 2+2+3=7 같은 경우를 빼줘야함
두유노우 어퍼바운드 로워바운드?
그럼 결과적으로 3가지 숫자를 만드는 경우를 모두 다 확인해야하나요??
혹시 조금만 더 구체적으로 설명가능하신가요 ㅠㅠ 두 가지 있는 걸 체크하는것까지는 알겠는데 그 뒷부분을 어떻게 해야될지 잘 감이안오네요
내가 추천하는 해법은 미리 전처리 후 lowerbound upperbound로 숫자 찾고 포제원리로 예외처리 해주는거임
아 근데 숫자 범위가 작아서 이진탐색안해도 되겠네
일단 숫자 3개가 모두 다른경우 / 2개만 같은경우 / 모두 같은 경우 나눠서 처리해봐
답변 감사합니다! 시아닌님, 0xrgb님 말씀하신대로 한번 더 풀어보겠습니다!