1. 부분합
1) 문제
문제 설명
빙10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <climits> #include <iostream> using namespace std; int N,S; vector<int> seq; int solve() { int left = 0, right = 0; int sum = seq[0]; int length = INT_MAX; while (true) { if (right > N-1) break; if (left > right) break; if (sum >= S) { length = min(length, right - left + 1); sum -= seq[left]; left++; } else { right++; sum += seq[right]; } } return length == INT_MAX ? 0 : length; } int main() { cin >> N >> S; for (int i=0; i<N; i++) { int val; cin >> val; seq.push_back(val); } int res = solve(); cout << res << "\n"; return 0; }
2. 구간 합 구하기
1) 문제
문제 설명
어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.
출력
첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <iostream> using namespace std; // 수의 개수, 변경이 일어나는 횟수, 구간합을 구하는 횟수 int N,M,K; vector<long long> seqs; vector<long long> segTreeVec; long long BuildTree(int node, int left, int right) { if (left == right) { segTreeVec[node] = seqs[left]; return seqs[left]; } int mid = (left + right)/2; return segTreeVec[node] = BuildTree(node * 2, left, mid) + BuildTree(node * 2 + 1, mid + 1, right); } void UpdateTree(int node, int left, int right, int index, long long diff) { if (left > index || index > right) return; if (left == right) { segTreeVec[node] += diff; return; } segTreeVec[node] += diff; int mid = (left + right) / 2; UpdateTree(node * 2, left, mid, index, diff); UpdateTree(node * 2 + 1, mid + 1, right, index, diff); } void UpdateTree(int index, long long num) { long long diff = num - seqs[index]; seqs[index] = num; UpdateTree(1, 0, N - 1, index, diff); } long long SumTree(int node, int left, int right, int tleft, int tright) { if (tleft <= left && right <= tright) return segTreeVec[node]; if (tleft > right || tright < left) return 0; int mid = (left + right) / 2; return SumTree(node*2, left, mid, tleft, tright) + SumTree(node*2+1, mid + 1, right, tleft, tright); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> N >> M >> K; for (int i=0; i<N; i++) { long long num; cin >> num; seqs.push_back(num); } segTreeVec.resize(4*N + 1); BuildTree(1, 0, N-1); for (int i=0; i<M+K; i++) { long long a,b,c; cin >> a >> b >> c; if (a == 1) UpdateTree(b-1, c); else if(a == 2) cout << SumTree(1, 0, N-1, b-1, c-1) << '\n'; } return 0; }
3. 집합
1) 문제
문제 설명
비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
all: S를 {1, 2, ..., 20} 으로 바꾼다.
empty: S를 공집합으로 바꾼다.입력
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
출력
check 연산이 주어질때마다, 결과를 출력한다.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <iostream> using namespace std; int M; int mask = 0; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> M; for (int i=0; i<M; i++) { string cmd; cin >> cmd; int num; if (cmd == "add") { cin >> num; mask |= (1 << num); } else if (cmd == "remove") { cin >> num; mask &= ~(1 << num); } else if (cmd == "check") { cin >> num; if ((mask & (1<<num)) == (1<<num)) cout << 1; else cout << 0; cout << '\n'; } else if (cmd == "toggle") { cin >> num; mask ^= (1 << num); } else if (cmd == "all") { mask = (1<<21)-1; } else if (cmd == "empty") { mask = 0; } } return 0; }
