algorithm (69) 썸네일형 리스트형 백준 1940번 주몽 https://www.acmicpc.net/problem/1940 아이디어:1. vector 사용2. 입력받은 vector에서 합이 되는 두 수 찾기3. 이중반복문으로 순회 // 1940#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long N, M, answer = 0; cin >> N >> M; vector A(N, 0); for (int i = 0; i > A[i]; } for (int i = 0; i 모범답안:1. 정렬 후 투 포인터 사용해서 시간복잡도 최적화 (84ms > 4ms)2. algorithm의 sort 함수에서 vec.. 백준 2018번 수들의 합 5 https://www.acmicpc.net/problem/2018 아이디어:1. N이라는 선형 연속된 숫자 스트림을 가리키는 시작 인덱스, 종료 인덱스 두 가지2. 시작지점은 둘 다 1을 가리키며, 합은 13. 합이 N보다 작으면 종료 인덱스 다음으로4. 합이 N보다 크면 시작 인덱스 다음으로5. 같으면 answer 1 추가, 종료 인덱스 다음으로6. N 자체도 카운트 // 2018#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, start_index, end_index, sum, answer; start_index = 1; end_index = 1; sum =.. 백준 10986번 나머지 합 https://www.acmicpc.net/problem/10986 아이디어:1. 1차원 long vector 생성.2. 합 vector S 생성, S 각 요소에 대해 M으로 나눈 나머지로 변경ex) 백준 예제 입력: 1 2 3 1 2 > 1 3 6 7 9 > 1 0 0 1 03. 먼저 나온 0은 하나씩 더해주기 = 34. 같은 나머지가 나온 요소에 대해서 조합 x C 2를 적용ex) 나머지 0인 요소가 3개이므로 3 C 2, 나머지 1인 요소가 2개이므로 2 C 2조합 = x * (x - 1) / 2같은 나머지가 나온 요소 쌍이 M으로 나누어 떨어지는 구간인 이유:구간 합 (i, j) = S[j] - S[i - 1](S[j] − S[i−1]) % M = 0(S[j] % M) − (S[i−1] % M) .. 백준 11660번 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 아이디어:1. 구간 합 구하기의 2차원 배열로 확장2. (2, 2) ~ (3, 4) 합은이 아닌이다.3. 원본 배열과 합 배열을 따로 만들고, 합 배열은 (1, 1)부터 (i, j)까지의 합으로 표현D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j]4. 원하는 구간 합 (x1, y1) ~ (x2, y2) = answeranswer = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + A[x1 - 1][y - 1] // 11660#include using namespace std;int table[1025][1025] = { {0} };int D[1.. 백준 11659번 구간 합 구하기 https://www.acmicpc.net/problem/11659 아이디어:1. 현재 인덱스 까지의 총 합을 구하는 배열 int S[] 생성2. S[i] = S[i - 1] + A[n] (ex A: 1 2 3 4 5, S: 1 3 6 10 15)3. 구간 i ~ j 까지의 합은 S[j] - S[i - 1]과 동일4. 문제의 인덱스에 맞춰 배열의 크기는 S[100001], 순회는 (int i = 1, i 5. S[0] 은 0으로 두고 S[1]부터 A[1] 과 동기화// 11659#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M, i, j; int A[1000.. 이전 1 ··· 6 7 8 9 10 11 12 ··· 14 다음
