본문 바로가기
반응형

전체 글1311

[BOJ] 백준 2670 연속부분최대곱 출처: https://www.acmicpc.net/problem/2670 Input 8 1.1 0.7 1.3 0.9 1.4 0.8 0.7 1.4 Output 1.638 ① N > N; for (int i = 0; i > arr[i]; for (int i = 0; i < N; i++){ sum = 1; for (int j = i; j < N; j++){ sum *= arr[j]; answer = answer.. 2021. 2. 28.
[Jungol] 정올 2306 두 용액 출처: [Jungol] 2306 두 용액 Input 5 -2 4 -99 -1 98 Output -99 98 같은 문제 다른 풀이: [BOJ] 2470 두 용액 [BOJ] 백준 2470 두 용액 출처: https://www.acmicpc.net/problem/2470 Input 5 -2 4 -99 -1 98 Output -99 98 ※ 같은 문제 다른 풀이: [Jungol] 2306 두 용액 [Jungol] 정올 2306 두 용액 출처: [Jungol] 2306 두 용액 Input 5 -.. zoosso.tistory.com ① 실제로 채점되는 Input Data는 정렬되어 있지 않기 때문에 주어진 숫자 정렬 ex) {-2 4 -99 -1 98} → {-99 -2 -1 4 98} ② 두 개의 인덱스 low.. 2021. 2. 28.
[BOJ] 백준 2470 두 용액 출처: https://www.acmicpc.net/problem/2470 Input 5 -2 4 -99 -1 98 Output -99 98 ※ 같은 문제 다른 풀이: [Jungol] 2306 두 용액 [Jungol] 정올 2306 두 용액 출처: [Jungol] 2306 두 용액 Input 5 -2 4 -99 -1 98 Output -99 98 같은 문제 다른 풀이: [BOJ] 2470 두 용액 ① 실제로 채점되는 Input Data는 정렬되어 있지 않기 때문에 주어진 숫자 정렬 ex) {-2 4 -99.. zoosso.tistory.com 가장 가까운 두 수의 합이 0에 가장 가까운 두 수를 구하는 것입니다. * 양수만 주어지거나 음수만 주어질 수도 있다 부호를 고려하지 않기 위해 절대값 기준으로 숫자.. 2021. 2. 28.
[Jungol] 정올 3429 로봇 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2751 Input 3 2 10 1 2 5 Output 1 로봇의 이동거리를 최소화하는 것이기 때문에 몇대의 로봇이든 움직이든 이동거리만 최소화하면 상관없습니다. 이 문제를 해결하기 위해서는 로봇의 감시 영역에 대한 구간합을 통해서 해결할 수 있습니다. 특정 지점에 두 개의 로봇이 놓일 수 없으며, 감시 영역을 최적화하기 위해 인접한 두 로봇의 감시 영역을 생각해보자. ▶ arr[i] = robot[i] - robot[i-1] - 2*R ex) 2 - 1 - (2×2) = -3 두 영역은 『-1』 만큼 겹처서 감시를 하고 있습니다. 감시 거리 R = 2인 상태에서 최적의 구간은 아래와 같습니다.. 2021. 2. 28.
[BOJ] 백준 10986 나머지 합 출처: https://www.acmicpc.net/problem/10986 Input 5 3 1 2 3 1 2 Output 7 부분합 psum을 이용해서 특정 구간합을 비교적 빠르게 구할 수 있지만, 이 문제의 경우 그렇게 하더라도 M으로 나누어 떨어지는 구간을 확인하기에는 TLE 발생 #include typedef long long LL; const int MAX_N = 1e6; LL psum[MAX_N + 10]; int ans; int main(void) { // freopen("input.txt", "r", stdin); int N, M, num; scanf("%d %d", &N, &M); for (int i = 1; i 2021. 2. 28.
[Jungol] 정올 3263 연속구간최대합(Circular) 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2556&sca=50&page=22 Input 10 4 5 -10 3 4 -7 -2 8 -6 -1 Output 10 * 대부분의 원형 문제는 직선으로 바꾸어 해결할 수 있다. 직선 구간에서 연속 구간의 최대합을 구하는 것은 DP를 이용해 빠르게 구할 수있습니다 원형으로 이루어져 있기에 해가 나올 수 있는 부분은 2가지 입니다. ① 중간 부분의 연속된 합 (DP로 빠르게 구할 수 있음) ② 끝 지점과 시작 시점이 포함되는 영역 즉, 직선에서의 연속구간 최대합은 ①만 고려해주면 되지만 원형이기 때문에 ②도 고려해주어야 합니다. ▶ ①과 ② 중 더 큰 값이 원형구간에서 최대값이 됩니다. Q. 시작과 끝이 .. 2021. 2. 28.
[Jungol] 정올 1836 연속부분합 찾기 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1109&sca=20 Input 4 1 2 -2 4 Output 5 #include const int LM = 100005; int N, ans, sum; int main(void) { // freopen("input.txt", "r", stdin); int i, num; scanf("%d", &N); for (i = 0; i 0) sum += num; else sum = num; if (ans < sum) ans = sum; } printf("%d\n", ans); return 0; } 2021. 2. 28.
[Jungol] 정올 2497 수열 출처: http://www.hancom.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1758&sca=50 Input 10 2 3 -2 -4 -9 0 3 7 13 8 -3 Output 21 psum[i] = 첫번째 원소부터 i번 원소까지의 구간합 ▶ A[i] = psum[i] - psum[i-1] ex) A[3] = -4 = psum[3] - psum[2] = -3 - 1 = -4 ▶ (K ≤ i) K 길이의 구간 합 = psum[i] - psum[i - K] ex) 구간 [8, 9] 합 = psum[9] - psum[7] = 19 - (-2) = 21 = A[8] + A[9] = 13 + 8 psum[9] - psum[7] = (1~9까지의 합) - (1~7 까지.. 2021. 2. 28.
[Jungol] 정올 3706 합이 0이 되는 연속구간 세기 출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3055&sca=99&page=24 Input 4 5 -5 -7 7 Output 3 ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것 zoosso.tistory.com 연속구간의 합을 구해야 한다는 점에서 prefix sum을 이용하면 좋을 것 같다는 생각이 듭니다. 간단하게 생각했을 때는 psum = 0인 개수만 찾으면 되지 않을까 생각할 수 있지만, psum = 0이 아니어도 문제에서 요구한 구간의 합 = 0.. 2021. 2. 28.
[Jungol] 정올 3136 const 구간의 합 구하기(2D) 출처: 정올(Jungol) Input 5 1 2 3 4 5 6 7 8 9 0 -1 2 1 1 1 5 2 3 1 4 1 0 1 0 1 3 2 1 2 1 3 3 5 5 1 1 5 5 Output 6 13 67 쿼리에서 묻는 (sri, sci) ~ (eri, eci)는 다음과 같습니다. ex) (3, 3) ~ (5, 5) ▶ 1 + 1 + 1 + 3 + 1 + 4 + 1+ 1 + 1 = 13 ★ DP[i][j] = (0, 0) ~ (i, j) 영역 합 각 영역을 구할 때, 이중 for문으로 구하면 TLE 발생 ▶ DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + x; (x = 해당 위치의 숫자를 의미합니다.) ex) DP[3][3] = 29 구한다고 가.. 2021. 2. 28.
반응형

티스토리툴바