algorithm (35) 썸네일형 리스트형 백준 1253번 좋다 https://www.acmicpc.net/problem/1253 아이디어:1. vector, 정렬, 투 포인터 사용2. 정수 범위이므로 음수 고려 > 끝 인덱스가 N - 1에서 시작3. 자기자신을 더할 때는 제외한다. // 1253#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long N, answer = 0; cin >> N; vector A(N, 0); long start = 0; long end = 0; for (int i = 0; i > A[i]; } sort(A.begin(), A.end()); for (int i = 0; i.. 백준 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.. 이전 1 2 3 4 5 ··· 7 다음
