2143번 - 두 배열의 합
단순하게 A의 부분합들을 모두 map에 저장 한 뒤,
B의 부분합들을 구하면서 T-부분합을 map에서 찾는 방식으로 풀었습니다.
다만 아래와 같이 타입을 전부 int로 선언했을 때에는 AC가 안나다가,
long long으로 바꾸고 나니 AC가 났는데,
문제 설명 상 수열의 각 원소의 값은 절댓값 1,000,000 이하, 수열의 최대 개수는 1,000개 이하,
T 역시도 1,000,000,000 이하이므로
문제 연산 중에 등장할 수 있는 수의 범위가 int 범위 안쪽으로 들어가는게 확실할텐데
int로는 AC가 안나오는게 이상하네요..
혹시 제가 빠뜨린 부분이 있을까요?
데이터가 의심되면 "이렇게 저렇게 바꿨더니 안 되던 게 된다"가 아니라, 데이터 자체를 검사하는 문장을 assert로 확인해 보는 것이 확실합니다.
말씀하신 부분들에서는 int를 넘는 곳이 없지만, 이 코드에서 문제가 되는 곳은 ans의 자료형입니다. A의 부분 배열을 고르는 방법이 약 50만 가지, B의 부분 배열을 고르는 방법도 약 50만 가지이므로 답은 최대 약 2500억까지 도달할 수 있습니다.
아하 역시 데이터 문제가 아니라 ㅠㅠ 간단한 곳에서 놓치고 있었군요
감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
ababc1005 4년 전
단순하게 A의 부분합들을 모두 map에 저장 한 뒤,
B의 부분합들을 구하면서 T-부분합을 map에서 찾는 방식으로 풀었습니다.
다만 아래와 같이 타입을 전부 int로 선언했을 때에는 AC가 안나다가,
long long으로 바꾸고 나니 AC가 났는데,
문제 설명 상 수열의 각 원소의 값은 절댓값 1,000,000 이하, 수열의 최대 개수는 1,000개 이하,
T 역시도 1,000,000,000 이하이므로
문제 연산 중에 등장할 수 있는 수의 범위가 int 범위 안쪽으로 들어가는게 확실할텐데
int로는 AC가 안나오는게 이상하네요..
혹시 제가 빠뜨린 부분이 있을까요?