본문 바로가기

PS87

백준 24518 / C++ https://www.acmicpc.net/problem/24518 24518번: 잘 알려진 합 구하기 주어진 수식의 값을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net [ 풀이 ] 몫이라는게 N에 가까워질수록 같은값이 점점 많아진다. 같은값이 나오는 구간을 묶어보자. [N/2+1, N] 은 몫이 모두 1이다. [N/3+1, N/2]은 몫이 모두 2이다. 이렇게 구간 나누는걸 sqrt(N)이 나올때까지 한다. 이제 sqrt(N)까진 그냥 f(i)g(i)를 계산하고 나머지 구간들은 몫이 같은 구간마다 나머지들을 곱해서 더해준다. 여기서 그냥 훑으면서 계산하면 O(N)이다. 나머지는 0, 1, ...., m-1이 반복된다는 성질을 통해, 구간마다 주기를 찾고 잘 처.. 2022. 8. 1.
백준 21909 / C++ https://www.acmicpc.net/problem/21909 21909번: Divisible by 3 For an array $[b_1, b_2, \dots , b_m]$ of integers, let’s define its weight as the sum of pairwise products of its elements, namely as the sum of $b_ib_j$ over $1 \le i < j \le m$. You are given an array of $n$ integers $[a_1, a_2, \dots , a_n]$, and a www.acmicpc.net [ 풀이 ] 문제의 정의에 나온 weight는 식으로 정리하면, 1/2*{(a[l]+....+a[r])^2 - (a[l]^.. 2022. 8. 1.
백준 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.

티스토리툴바