전체 글188 백준 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. dp with 포함배제 원리 포함배제 원리를 이용하는 dp문제 2개를 풀어보자. 1. BOJ 14517 https://www.acmicpc.net/problem/14517 14517번: 팰린드롬 개수 구하기 (Large) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 승수는 주 www.acmicpc.net [ 풀이 ] 문제를 잘 이해해야 한다. 부분수열이므로 연속된 팰린드롬일 필요가 없다. 맨처음과 끝에서 시작해서 좁혀가면서 갱신해주면 된다. dp[s][e]:=구간 [s,e]를 볼 때 팰린드롬의 총 개수라고 정의하면, 상태전이는 3가지가 있다. 1. s를 사.. 2022. 8. 1. 이전 1 ··· 40 41 42 43 44 45 46 47 다음