알고리즘/누적합2 [백준 11660] 구간 합 구하기 5 / 자바 / 누적합 문제 레벨: 알고리즘: 누적합풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/116601 번째 시도 이 문제는 이차원배열의 누적합이다.알고 가야 할 것은 일차원 배열의 누적합과 배열에 담기는 값이 다른 거이다. 혹시 O 위치의 담길 값이 ---->를 다 더한 값이라고 생각할 수 있다. 그건 틀렸다. ----------->O우린 1,1,를 좌상 꼭지점으로 O을 우하 꼭지점으로 삼는 직각삼각형의 합으로 생각해야 한다.합을 화살표 표시하고 그림으로 나타내면 아래와 같다------ --->O 위 그림을 보면서 배열에 들어가는 값을 이해해보자.빨간색 위치에 배열값은 초록색 + 파란색 - 노란색(겹치는 부분)이다. 이 공식으로 배열을 채우면 된다. .. 2024. 6. 12. [백준 11659] 구간 합 구하기 4 / 자바 / 누적합 문제 레벨: S3알고리즘: 누적합풀이시간: 16분힌트 참조 유무: 무https://www.acmicpc.net/problem/116591 번째 시도 문제를 보고 엥 이거 너무 기초적인 문제 아니야? 라고 생각했다가 제한을 보고 생각을 바꿨다. 100,000(N의 최댓값) x 100,000(M의 최댓값) = 100,000,000,000(1억 초과)이기 때문에 O(n^2) 시간복잡도로는 풀 수 없다. [아이디어]O(N) 시간복잡도를 생각해봤다. 한번에 탐색으로 1 ~ arr[i]까지 담길 배열을 만드는 것이다. 만약 3~5까지 합을 구하고 싶다면 5인덱스에 있는 값(1~5) - 2인덱스에 있는 값(1 ~ 2)로 구하면 되는 것이다.import java.util.*;import java.. 2024. 6. 12. 이전 1 다음
