프로그래밍/백준(BOJ)

[백준(BOJ) / C++][Silver Ⅳ] 1940번 : 주몽

문제https://www.acmicpc.net/problem/1940풀이정렬 알고리즘으로 계산하기 편하게 정렬한 후 start_point 하고 end_point 의 합을 M과 비교하며 크면 end_point를 줄이고 작다면 start_point를 올리며 만약 M과 같았을때 count에 1를 더하며 start_point, end_point 각각을 +1, -1을 해준다.소스코드 #include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; int count, start_point, end_point; cin >> N >> M; vect..

[백준(BOJ) / C++][Silver Ⅴ] 2018번 : 수들의 합 5

문제https://www.acmicpc.net/problem/2018풀이1. 숫자를 가리키는 포인터 두개(start_index, end_index)를 준비한다.2. 해당 포인터 사이의 값(sum)에 따라 포인터를 옮겨준다.2-1. sum > Nsum의 값이 N 보다 높을 경우 sum의 값을 현재 start_index 값만큼 줄여주고 start_index 값을 올려준다.sum = sum - start_index;start_index++;2-2. sum sum의 값이 N 보다 작을 경우 end_index 를 높여주고 그 후 end_index의 값을 더해준다.end_index++;sum = sum + end_index;2-3. sum == Nsum의 값이 N과 같을 경우 해당 합은 맞다는 뜻이므로 count를..

[백준(BOJ) / C++][Gold Ⅲ] 10986번 : 나머지 합

문제https://www.acmicpc.net/problem/10986풀이해당 문제는 구간 합, 경우의 수를 알고있다면 풀 수 있는 문제 입니다.소스코드#include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N >> M; vector S(N, 0); vector C(M, 0); long answer = 0; cin >> S[0]; for(int i = 1; i > temp; S[i] = S[i-1] + temp; } for(int i = ..

[백준(BOJ) / C++][Silver Ⅰ] 11660번 : 구간 합 구하기 5

문제https://www.acmicpc.net/problem/11660풀이해당 문제는 구간 합 알고리즘을 사용하여 해결하였습니다. 먼저, 질의의 개수가 100,000개 이므로 이 문제는 질의마다 합의 값을 구하면 안된다. 그렇게 되면 무조건 시간초과가 나오기 때문에 다른 방법을 찾아봐야 하는데, 그것이 바로 '구간 합 배열' 이다. 이 문제는 2차원 구간 합 배열을 사용해야하는데, 해당 배열은 다음과 같이 정의할 수 있다. D[X][Y] = 원본 배열의 (0, 0) 부터 (X, Y) 까지의 사각형 영역 안에 있는 수의 합. 일단, 합 배열을 만들어야 하는데,  2차원 구간 합 배열의 1행, 1열부터 구합니다.구간 합 배열 1행, 1열은 다음과 같이 구합니다. 1행 : D[1][j] = D[1][j-1] ..