www.acmicpc.net/problem/20002
알고리즘💻/누적합&투포인터
www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 아이디어: 부분합을 이용하면 되지 않을까. 2k+1만큼의 길이를 더하면서 최댓값을 갱신한다.. 일단 ice배열을 1,000,000개씩 만들고, g와 x를 받으면서 ice[x]=g를 넣는다. 그리고 큐를 하나 만들어서 ice를 하나씩 추가하고 길이가 2k+1이 되면 하나씩 pop하고 다음 걸 더한다. 이때 최댓값을 갱신해준다. 간단한 문제인데.. 이렇게 막막하면 우짤꼬....ㅠㅠ #게으른 백곰 import sys from collect..
www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 아이디어: 뭔가 일단 정렬을 해야 할 것 같다. 근데 이걸 투 포인터로 어떻게 풀 수 있을까? 모든 경우를 찾아본다면, 가능한 두 수를 모두 뽑고 그 합과 같은 숫자가 있는지 탐색할 수 있을 것이다. 탐색은 이분 탐색이 가능할 것 같다. 근데 이게 시간 안에 풀어질까..? 그래서 구글링함^^ 내 생각이 조금은 맞았다. 대신 반대로, arr에 있는 모든 수를 돌면서 합이 arr[i]가 되는 두 수가 있는지를 찾는다. 이때 투 포인터를 이용한..
www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 아이디어: G = 현재 몸무게^2 - 기억하던 몸무게^2 현재 몸무게와 기억하던 몸무게가 뭐든 될 수 있으니까..(이게 무슨..) 자연수의 제곱 중에서 투포인트를 사용해서 차가 G가 되는 경우를 구하자. 일단 가능한 몸무게의 배열을 만들고 (1~200000까지의 제곱) result, left, right 모두 0으로 초기화한다. result가 g보다 큰 경우 left++, 작은 경우 right++ import sys ..
www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 아이디어: 투 포인트로 구현하면 되고, 대충 로직은 강의 들으면서 이해했는데 구현 과정에서 애를 먹었다. 이래서 어설프게 알면 안돼..ㅠㅠ left, right 포인터를 0, 0 으로 초기화하고 합result와 출력할 답 ans 도 0으로 초기화한다. 무한루프를 돌면서 합이 m보다 클 경우에는 합을 줄여야 하므로 result에서 arr[left]값을 빼고 left++한다..
www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 아이디어: prefix sum(누적 합)을 이용하..
