PS/BOJ57 백준 21757 / C++ https://www.acmicpc.net/problem/21757 21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net [ 풀이 ] dp[i][j]를 i번째 인덱스까지 j개로 분할하는 방법의 수라고 놓자. 상태전이 시켜보자. i번을 안쓰는 경우 그냥 dp[i+1][j]로 넘어간다. i번을 사용하는 경우 dp[i+1][j+1]로 넘어간다. 사용할 수 있는 경우는 문제조건에 따라 잘 체크하면 된다. 그리고 매번 i번에서 i+1만 참조하므로 토글링으로 공간복잡도를 조금 줄여줄 수 있다. .. 2022. 8. 1. 백준 12899 / C++ https://www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net [ 풀이 ] 값을 인덱스로, 그 값의 개수를 저장하는 세그트리를 만들어주자. (값을 인덱스로 세팅하는 방식은 자주 사용되는 방법이니 알아둡시다.) 중복에 주의하자. 이미 있는 수도 추가해줘야 X번째로 작은 수를 찾을 수 있다. 저장된 곳에서 X번째로 작은수는 값이 인덱스로 세팅된 세그트리에서 X번째 수를 찾으면 된다. [ Code ] #include using na.. 2022. 8. 1. 백준 15561 / C++ / 구간합 최댓값 쿼리 O(logN)에 처리하기 https://www.acmicpc.net/problem/15561 15561번: 구간 합 최대? 2 첫 번째 줄에 정수 N과 Q, U, V가 입력된다. (1 ≤ N, Q ≤ 105, - 5 ≤ U, V ≤ 5) 두 번째 줄에 정수 K1, K2, ..., KN이 주어진다. (-102 ≤ Ki ≤ 102) 세 번째 줄부터 쿼리가 www.acmicpc.net [ 풀이 ] 이제 이 문제의 합의 최댓값 구하기를 O(logN)에 처리해보자. 연속구간합의 최댓값은 잘 알려진 방법을 통해 O(logN)에 처리할 수 있다. 자세한 설명(https://seungwuk98.tistory.com/39) 은 이곳을 참고하자. [ Code ] #include using namespace std; using ll = long l.. 2022. 8. 1. 백준 15560 / C++ https://www.acmicpc.net/problem/15560 15560번: 구간 합 최대? 1 첫 번째 줄에 정수 N과 Q, U, V가 입력된다. (1 ≤ N, Q ≤ 103, - 5 ≤ U, V ≤ 5) 두 번째 줄에 정수 K1, K2, ..., KN이 주어진다. ( - 102 ≤ Ki ≤ 102) 세 번째 줄부터 쿼 www.acmicpc.net [ 풀이 ] 식을 정돈하자. 누적합 psum으로 정리하면.. U*(psum[j]-psum[i-1])+V(j-i)이다. 왠지 U*psum[i]+V*i 를 다시 f(i)로 놓고 싶다. 그러면 식은 f(j)-f(i-1)-V가 된다. 이제 문제는 구간 [A,B]에서 f(j)-f(i-1)의 최댓값을 구하면 된다. O(N)에 해결하자. dp[j]를 f(j)-f(i.. 2022. 8. 1. 이전 1 ··· 7 8 9 10 11 12 13 ··· 15 다음