본문 바로가기

누적합23

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.
백준 20438 자바 - 출석체크 (BOJ 20438 JAVA) 문제 : https://www.acmicpc.net/problem/20438 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/20400/BOJ_20438.java 1. 일단 잠자는 사람들을 생각하지 않고, 출석 코드를 보내는 부분만 생각해보자. n명을 입력받고, q를 입력받아 단순히 자신과 그 배수들은 출석코드를 받았다고 할 수 있다. 이 부분까진 간단하게 구현 가능할 것이다. 2. 다음으로 잠자는 사람에 대해 어떻게 처리해야할지 확인해보자. 일단 q명 중 출석코드를 받은게 자는사람에 포함되어 있다면 그 배수한테 출석코드를 보낼 수 없다. 따라서 이 경우 해당 출석 코드는 무시된다. (23line) 다음으로, 출석 코드를 받은 사람은.. 2021. 10. 23.

티스토리툴바