0과 1의 쉼터

문제https://boj.ma/12841 12841번: 정보대 등산 boj.ma 풀이왼쪽의 1번부터 오른쪽 N번까지 횡단보도를 하나만 건너서 갈 때 최소 거리를 구하는 문제다.횡단보도를 제외한 나머지 구간의 합을 매번 구하면 시간초과가 발생한다.누적합을 미리 계산해 주자.최대 거리가 10만인 10만 개의 구간의 주어진다. long을 사용하자. // Solve long[] prefixSumL = new long[N]; long[] prefixSumR = new long[N]; for (int i = 1; i 첫 번째 횡단보도부터 시작해서 N번째 횡단보도까지 하나씩 건너보자.총 거리는 횡단보도를 건너기 전 왼쪽 구간의 합 + 횡단보도 길이 + 횡단보도를 건넌..

문제https://www.acmicpc.net/problem/23827 풀이주어진 수열에 대해 1 ≤ i 수가 너무 커질 수 있으니 1e9 + 7로 나눈 나머지를 출력해야 한다.문제를 만족하는 정수쌍 곱의 합은 i와 i + 1 ~ j의 합의 곱과 같다.최대 길이가 50만인 수열에 대해 누적합을 미리 구해 // Solve final int MOD = (int) (1e9 + 7); long[] prefixSum = new long[N]; prefixSum[0] = A[0]; for (int i = 1; i 모든 i에 대한 A[i] * ( prefixSum[N] - prefixSum[i] )을 구하면 된다. long res = 0; ..

문제민균이에게는 ‘빚쟁이’ 라는 별명이 있다. 이 별명은 악덕 사채업을 하는 김우현연구소에서 민균이가 빌린돈을 잘 갚지 않는다고 하여 붙여준 이름이다. 민균이가 최근 N (1 ≤ N ≤ 4000) 번 돈을 빌렸고, 그때마다 빌린 돈이 각각 A(1), A(2), …, A(N) (1 ≤ A(i) ≤ 104) 라고 하자. 악덕 사채업소 김우현 연구소는 이름만큼이나 빌린 돈을 갚는 방식이 독특하다.먼저, 김우현 연구소가 민균이에게 M번 (1 ≤ M ≤ N) 의 빚을 갚으라고 명령하면, 민균이는 N번중 아무렇게나 M 번을 고르고, 고른 것 중에서 가장 많은 돈을 빌렸을 때 빌린돈 x M 을 갚아야 한다. 이렇게 하면 민균이가 김우현 연구소에 갚아야 하는 돈은 (빌린돈 + 추가적으로 더 갚아야 할 돈) 이 된다. ..

문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.풀이주어진 배열에 대한 구간 합을 구하는 문제다.최대 N = 1e5, M = 1e5 이므로 매번 구간 합을 구하면 시간초과가 발생한다. 부분합을 미리 구해주자.j번째 까지의 합에서 i - 1까지의 합을 빼야 한다. 출력 횟수가 많으므로 한번에 출력하자.소스코드보기출처https://www.acmicpc.net/problem..