나그네

29767번: 점수를 최대로 문제 https://www.acmicpc.net/problem/29767 29767번: 점수를 최대로 단대소프트고에는 교실 $N$개가 있다. 교실은 $1$번부터 $N$번까지 $1, 2, \ldots, N$ 순서로 연달아 있다. 학교 밖에는 $K$명의 학생들이 있다. $K$명의 학생은 학교에 들어가기 전 학생마다 목적지 교실 www.acmicpc.net 풀이 목적지 i번 교실에 도착하면 1~i번 방의 점수를 얻습니다. 즉, 누적합 배열로 i번 교실을 목표로 했을 시 얻는 점수를 저장합니다. K명의 학생들은 서로 다른 목적지를 가지므로 누적합 배열을 내림차순 정렬하고 앞에서부터 K개 원소의 합을 출력하면 됩니다. 코드 #include using namespace std; #def..

16507번: 어두운 건 무서워 문제 https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 풀이 [백준 / BOJ] C++ 11660 구간 합 구하기 5와 같은 문제다. [백준 / BOJ] C++ 11660 구간 합 구하기 5 11660번: 구간 합 구하기 5 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해..

11441번: 합 구하기 문제 https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 풀이 최대 10만 개의 연속된 수의 합을 구해야 한다. 따라서 입력과 동시에 모든 구간 합을 구할 수 있도록 구현이 가능한 누적 합 배열을 만들어 해결할 수 있다. 누적 합 알고리즘은 수열의 합 Sn에 대해 Sn - Sm-1 이 Am ~ An까지의 합과 같음을 이용하는 알고리즘이다. 코드 #inc..

27968번: 사사의 사차원 사탕 봉지 문제 https://www.acmicpc.net/problem/27968 27968번: 사사의 사차원 사탕 봉지 첫 번째 줄에 아이의 수 $N$과 사사가 사탕을 꺼내주려고 하는 최대 횟수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 300 \, 000$, $1 \le M \le 300 \, 000$) 두 번째 줄에 사사가 한 번에 사탕을 꺼내는 www.acmicpc.net 풀이 누적 합 + 이분 탐색 문제로 사탕을 꺼낼 때마다 사탕의 수는 누적되므로 몇 번 꺼냈을 때 사탕이 얼마나 있는지 알 수 있다. 그리고 아이가 받고 싶어하는 사탕의 수가 정확히 꺼낸 수와 동일하지 않을 수 있으므로 lower_bound 함수로 최초로 같거나 큰 수의 사탕이 있..

2143번: 두 배열의 합 문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 n과 m이 최대 1000이므로 가능한 모든 부분합을 구한 다음 가능한 조합의 수를 구하면 된다. 즉, A 부분합 배열의 각 원소에 대해 T가 되기 위해 필요한 수가 B 부분합 배열에 몇 개가 있는지 확인한다. B 부분합 배열을 오름차순 정렬한 후 lower_bound, upper_..

17425번: 약수의 합 문제 https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 풀이 예전에 모든 수의 약수의 합을 에라토스테네스의 체를 사용해 구하는 법을 9213번 문제를 통해 만들어봤다. [9213 꽤 좋은 수 해설] 링크를 참고해 주길. 어떤 수 A은 A의 배수의 약수다. 범위 내 모든 A의 배수에 A을 더해준다. 그러면 sieve의 A번 인덱스에는 A의 모든 약수의 합을 값으로 가..

11659번: 구간 합 구하기 4 문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 기본적인 누적합 배열을 통해 구간 합을 구하는 문제다. 누적 합 배열은 0번 인덱스의 값은 0이고 각 인덱스의 값이 현재까지 입력받은 수의 합인 배열이다. 예를 들어 입력받는 수가 1 2 3 4 5 라면 누적합 배열은 [0, 1, 3, 6, 10, 15]가 된다. 여기서 i번째 원소부터 j번째 원소까지의 합을 구하기 위해서는 ar..

1806번: 부분합 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 부분합이 S 이상인 부분합 중 길이가 가장 작은 것의 길이를 구하는 문제다. 시간복잡도가 O(N^2)인 알고리즘으로 풀면 시간 초과를 받는다. 따라서 O(N)인 알고리즘으로 풀어야 한다. 그중 하나가 투 포인터를 사용해서 푸는 방법이다. left와 right를 모두 0으로 두고 sum = v[0]으로 초기값을 설정한다. 합(sum)은 인덱스가 left부..

27496번: 발머의 피크 이론 문제 https://www.acmicpc.net/problem/27496 27496번: 발머의 피크 이론 각 시간에 따른 혈중 알코올 농도는 {0.045, 0.089, 0.133, 0.131, 0.127}이다. 따라서 지금으로부터 2시간 후와 3시간 후, 총 두 시간 동안 혈중 알코올 농도를 유지할 수 있다. www.acmicpc.net 풀이 대회 때 누적합으로 풀었다가 빼는 배열의 크기를 제한하기 어려웠다. 그래서 그냥 더하다면서 배열에 더한 값을 저장하고 시간이 지속 시간보다 커지면 차례대로 빼가면서 범위를 만족하는지 확인했다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin...

11660번: 구간 합 구하기 5 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 2차원 배열에서 (x1, y1)부터 (x2, y2)의 합을 출력하는 문제다. 가장 먼저 떠오른 생각은 행 별로 누적 합(prefix sum)을 먼저 구하는 것이었다. 이후 x1, y1, x2, y2를 입력받고 각 행별로(x1, ... , x2) 열의 누적 합(sum[y2] - sum[y1 - 1])을 답에 더해..