개발하는 개구리

🐸 문제 정보 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 🤖 알고리즘 누적합 ⏱️ 풀이 시간 13.22m 📝 풀이 그래프를 그려보고 누적합 테이블을 구하는 원리와, 답을 찾는 원리를 알아냈더니 쉽게 풀 수 있었다. 누적합 테이블 구하기 pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] 구간 합 구하기 pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 ..

🐸 문제 정보 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 🤖 알고리즘 누적합, 투포인터 ⏱️ 풀이 시간 12.12m 📝 풀이 누적합으로 풀면 간단하지만, 구할 수 없는 경우 0 출력 처리 때문에 약간의 시간 낭비를 했다. 주어진 입력 리스트를 누적합으로 만들고, 투포인터를 돌면서 아래 조건에 따라 처리하면 된다. start와 end 사이의 합이 s보다 크거나 같다면, 길이에 대해 최소값 처리를하고 start를 뒤로 한 칸 이동 start와 end 사이의 합이 s보다 작다면, end를 뒤로 ..

🐸 문제 정보 20159번: 동작 그만. 밑장 빼기냐? 카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다. 둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다. www.acmicpc.net 🤖 알고리즘 누적합 ⏱️ 풀이 시간 47.56m 📝 풀이 구현이 껴있는 누적합 문제였다. 문제를 읽자마자 누적합으로 풀어야한다는 것은 바로 알았으나, 이를 구현해내기까지 조금 헤맸다. 헤맨 이유는 '상대의 패도 밑장 뺄 수 있다' 라는 전제 때문이었다. 문제에 전혀 명시가 안되어있고, 마치 내 패에서 밑장을 뺄 수 있는 것처럼 작성되어있지만, 상대에 패에서도 밑장을 뺼 수 있음을 알아야 한다. 홀수 인덱스끼리, 짝수 인덱스끼리 누적합을 구해서..