본문 바로가기

Prefix Sum28

백준 2003 자바 - 수들의 합 2 (BOJ 2003 JAVA) 문제 : boj2003 우선 i번째 수 부터 j번째 수까지의 합을 쉽게 알 수 있는 방법을 생각해보자. 누적합을 미리 구해둔다면 O(1)에 i번째 수부터 j번째 수까지의 합을 구할 수 있다. 예를들어 '4 7 2 1'을 확인해보자. 다음과 같이 누적합 배열(arr)을 마련해두면, i번째부터 j번째 수까지의 합은 arr[j]-arr[i-1]로 O(1)에 바로 구할 수 있다. 그럼 이제 합이 m이 되는 경우의 수를 구해야 한다. 더 효율적으로 하려면 투 포인터 개념을 활용하면 되지만, 이 문제의 경우 그냥 모든 경우를 확인하면 된다. 즉 i=1일 때 j=i~n의 모든 경우, i=2일 때 j=i~n의 모든 경우, ... i=n일 때 j=i~n인 모든 경우를 다 보면 된다. 코드 : github import j.. 2022. 3. 23.
백준 1450 자바 - 냅색문제 (BOJ 1450 JAVA) 문제 : boj1450 1. 문제 접근 딱히 냅색과 관련없어 보이는 문제이다. N이 작아 쉽게 풀 수 있을 줄 알았다. 근데 당연하게도 모든 경우를 보면 O(2^30) 이므로 통과할 수 없다. 그렇다고 냅색처럼 DP로 풀자니 1~10^9 까지 확인해야 할 것 같으니 역시 통과할 수 없다. bit DP쪽으로도 딱히 떠오르지 않았다. 그래서 이 문제에서 적용한 방식처럼 반반을 나눠서 생각해보기로 했다. 1.1 최대 30개의 데이터를 대충 반반으로 15개씩 나눈다(사실 한쪽을 25개, 한쪽을 5개로 해도 상관없다.). 이걸 A와 B라 하겠다. 1.2 A에 대해 나올 수 있는 모든 무게 합의 경우의 수 확인하고 어딘가에 저장한다. 이 경우 최대 15번에 대해 해당 수를 포함하거나 포함하지 않거나의 2가지 경우이.. 2022. 1. 22.
백준 10373 자바 - Buffcraft (BOJ 10373 JAVA) 문제 : boj10373 1. 문제 정의 상당히 문제가 불친절하다. 예제라도 의미 있을 예제를 들어주면 좋을텐데 ㅡㅡ; 상당히 별로인 문제이다. 1.1 'The following line must contain n different numbers', 'The last line of the output must contain m different numbers' 에 따라 출력을 해줘야 하는데, 그럼 following line이 0이라 출력할 게 없으면 줄을 띄워야 되나 말아야 하나라는 문제점이 있다(second, third line이라고 하던지.. 저렇게 하면 사실 following line이 last line이 되기도 하므로 애매하다.). 원래 문제대로라면 줄을 띄워야 맞지만(해당 대회 문제 채점 데이터.. 2022. 1. 17.
백준 2293 자바 - 동전 1 (BOJ 2293 JAVA) 문제 : boj2293 1. 우선 문제를 좀 더 간단히 변경해서 봐보자. 1,2,5의 가치를 가지는 동전이 있고, 그 가치의 합이 10이 되게 하려 한다. 그리고 문제와 다르게 동전의 구성이 같아도 순서가 다르면 다른 경우로 치고 생각해보자. 그럼 1차원 배열을 활용한 dp로 아래와 같이 풀 수 있다. (냅색 문제처럼 풀면 된다.) 1.1 우선 초기값이다. dp[idx]는 1,2,5의 동전들을 가지고 idx의 가치를 가지는 경우의 수를 나타낸다. dp[0]은 실제론 불가하지만, 초기값으로 넣어준다. 그래야 동전 하나를 가지고 표현할 수 있는 경우에 대해서도 별도로 처리하지 않고 점화식 하나로 계산하기 편하다. (예를들어 2의 가치를 표현하려면 동전2짜리 하나만 쓸 수 있다. 식으로는 dp[2-2]이다. .. 2021. 12. 29.
백준 20159 자바 - 동작 그만. 밑장 빼기냐? (BOJ 20159 JAVA) 문제 : boj20159 1. 정훈이가 받을 차례에 밑장빼기 한 경우 기본 아이디어는 직접 밑장빼기를 할 때 어떤 카드를 주게되는지 그려보면서 해보면 어렵지 않게 찾을 수 있다. 예제 입력 1 (3 2 5 2 1 3)을 홀수번째 카드(원래 정훈이가 받을 카드)와 짝수번째 카드(원래 상대방이 받을 카드)로 나눠서 그려보자. 그럼 밑장빼기를 하지 않는다면 다음과 같이 3, 5, 1을 받게 된다. 그럼 5번을 받을 차례 때 밑장빼기를 하면 어떻게 될까? '5'를 받을 차례에 짝수번째의 마지막에 있는 '3'을 받고, 이후 순서가 변경되면서 짝수번째를 정훈이가 받게 된다. 따라서 밑장빼기를 한 이후로는 짝수번째 카드를 받게 된다. 이런식으로 모든 경우를 다 그려보면 다음과 같다. 2. 정훈이가 상대방한테 밑장을 .. 2021. 12. 20.
백준 2143 자바 - 두 배열의 합 (BOJ 2143 JAVA) 문제 : boj2143 1. 부 배열을 이따 생각하고, 일단 X랑 Y라는 두 배열이 있는데 두 배열의 각 원소를 하나씩 더한 합이 T가 되는 경우부터 생각해보자. 아래와 같은 X, Y 배열이 있다. 1.1 가장 간단히 X[i] + Y[j] 가 T가 되는걸 찾는 방법은 모든 X의 원소에 대해 Y의 모든 경우의 수를 전부 확인해보면 된다. X[0]+Y[0] 확인, X[0]+Y[1] 확인, ... , X[1]+Y[0] 확인, X[1]+Y[1]확인, ... X[2]+Y[3] 확인. 이 경우 X의 개수 * Y의 개수 만큼 봐야 한다. O(XY) 1.2 1.1보다 더 빠르게 할 수 있는 방법이 있다. Y를 정렬한 후 O(YlogY), 각 X에 대해 T-X[i]가 Y에 있는지를 이분탐색으로 찾는 방식이다. 이 경우 .. 2021. 12. 13.
CodeForces 1569A - Balanced Substring (Java) 문제 : https://codeforces.com/contest/1569/problem/A 1. 입력을 받은 값에 대해 a와 b가 나온 횟수를 prefix sum으로 계산해둔다. -> 범위 내의 a와 b의 개수를 빠르게 구하기 위해 2. 그 후 모든 substring에 대해 누적합 배열에서 범위합이 동일한 경우가 있는지 확인한다. 코드 : github import java.io.DataInputStream; import java.io.IOException; public class Main { public static void main(String[] args) throws Exception { initFI(); int tc = nextInt(); StringBuilder sb = new StringBui.. 2021. 11. 27.
백준 11969 자바 - Breed Counting (BOJ 11969 JAVA) 문제 : https://www.acmicpc.net/problem/11969 breed 1,2,3에 각각 범위 내에 포함된 카운팅값의 합을 출력하면 된다. prefix sum을 활용하면 풀 수 있다. breed1,2,3로 나누어서 카운팅한 값의 누적합을 저장하는 방식으로 진행하면 된다. 예제 입력1에 대해 그려보면 다음과 같다. N번 소에 대해 breed1,2,3를 사용했음을 기입한 것이다. 이걸 breed 1,2,3에 대해 각각 누적합을 구해보면 다음과 같다. 이렇게 전처리로 누적합을 구해두고, 각 쿼리의 a, b값에 대해 범위내의 합계를 출력해주면 된다. 예를들어 a=2, b=4라면 breed1의 경우 breed1[b] - breed1[a-1] = 2 - 0 = 2, breed2의 경우 마찬가지로 1.. 2021. 11. 24.

티스토리툴바