누적합8 [SWEA] 2001번 - 파리 퇴치 [Java] https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq 1. 아이디어 N의 크기가 작아서 배열의 각 점에서 파리채를 전부 내리쳐보는 브루트포스 알고리즘으로 해결이 가능하고 누적합 배열을 활용해도 해결이 가능하다.2. 문제풀이 브루트포스는 배열의 해당 점이 파리채의 왼쪽 위가 위치한다고 가정하고 4중 for문을 활용했다. 누적합 배열은 2차원 누적합으로 1행 1열부터 r행 c열까지 두 점을 대각점으로 하는 직사각형의 넓이가 저장되게 했다.3. 코드 import java.io.*;import java.util.*;public class Solution { public static void .. 2025. 2. 13. [백준] 11441번 - 합 구하기 [Java] https://www.acmicpc.net/problem/11441 1. 아이디어 구간의 합은 누적합 배열로 간단하게 구할 수 있다.2. 문제풀이 구간의 양 끝을 포함해야해서 A-1로 설정하는 것만 주의해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(.. 2025. 2. 2. [백준] 11660번 - 구간 합 구하기 5 [Java] https://www.acmicpc.net/problem/11660 1. 아이디어 누적합 배열을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 주어진 영역에 대해 특정 영역의 합을 반복해서 구하는 문제로 2차원 누적합 배열을 생성한 후 prefixSum[x2][y2] - prefixSum[x2][y1] - prefixSum[x1][y2] + prefixSum[x1][y1] 점화식으로 간단하게 특정 영역의 합을 구할 수 있는 점을 활용해 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReade.. 2025. 1. 21. [백준] 11659번 - 구간 합 구하기 4 [Java] https://www.acmicpc.net/problem/11659 1. 아이디어 누적합 배열을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 주어진 수열에 대해 특정 구간의 합을 반복해서 구하는 문제로 누적합 배열의 두 원소의 차로 구간 합을 간단하게 구할 수 있는 점을 활용해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = .. 2025. 1. 21. [백준] 2003번 - 수들의 합 2 [Java] https://www.acmicpc.net/problem/2003 1. 아이디어 누적합과 브루트포스 알고리즘을 통한 방법과 투 포인터 알고리즘을 활용한 방법으로 해결할 수 있었다.2. 문제풀이 - 누적합 + 브루트포스 알고리즘주어진 문제가 수열에서 특정 구간의 합이 M이 되는 경우의 수를 구하는 문제이므로 누적합 배열을 미리 만든 후 2중 for문을 활용해 누적합 배열에서 두 원소의 차를 계산하는 방식으로 특정 구간의 합을 간단하게 구할 수 있다. - 투 포인터 알고리즘주어진 수열이 자연수로만 이루어진 수열이어서 두 개의 포인터를 앞쪽에서 출발시켜 두 포인터의 위치를 합을 구할 구간이라 생각하면 합을 줄이기 위해서는 왼쪽 포인터를, 합을 늘리기 위해서는 오른쪽 포인터를 오른쪽으로 이동시키는 것으로 볼 .. 2025. 1. 17. [백준] 2851번 - 슈퍼 마리오 [Java] https://www.acmicpc.net/problem/2851 1. 아이디어 누적합을 활용한 브루트포스 알고리즘으로 해결할 수 있다.2. 문제풀이 슈퍼 마리오는 처음부터 중단하기 전까지 버섯을 집어야하므로 이를 누적합 배열로 구했다. 누적합을 구하면서 바로 브루트포스 알고리즘으로 정답 및 100과의 차이를 저장하는 ans, diff 변수를 활용해서 100과의 차이의 절댓값이 더 작으면 해당 수를 정답으로 하고 절댓값이 같으면 정답과 해당 수 중 더 큰 수를 저장하도록 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReade.. 2025. 1. 17. [백준] 2559번 - 수열 [Java] https://www.acmicpc.net/problem/2559 1. 아이디어 연속된 날짜에서 온도의 합의 최댓값을 구해야하는 문제로 구간의 길이가 고정되어 있어서 누적합을 활용해서 해결했다.2. 문제풀이 누적합 배열을 만들고 순회를 하며 온도의 최댓값을 갱신해나가며 정답을 찾으면 간단하게 해결할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringToken.. 2024. 12. 2. [백준] 11399번 - ATM [Java] https://www.acmicpc.net/problem/11399 1. 아이디어 인출하는데 걸리는 시간이 짧은 사람부터 인출을 하는게 전체 인출시간의 합이 최소가 된다는 점을 활용한다.2. 문제풀이 앞에 인출한 사람이 걸린 시간만큼 뒷사람들이 영향을 받으므로 인출하는데 걸리는 시간이 짧은 사람부터 인출하도록 정렬을 해준다. 이후 정렬된 배열의 누적합 배열을 구하면 각 사람이 인출하는데 걸리는 시간을 구할 수 있고, 누적합 배열의 총합이 인출하는데 걸리는 전체 시간이 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 12. 2. 이전 1 다음
