본문 바로가기

전체 글188

백준 1126 / C++ https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net [ 풀이 ] dp를 세워보자. 우선 인덱스는 필수조건이다. 그리고 높이를 알아야 하는데 두개의 높이를 모두 저장할 수 없다. 한 개의 높이만을 저장한다면 나머지 역시 알 수 없다. 높이의 차이를 저장하면 깔끔하게 해결된다. dp[i][j]를 i번 블록을 선택할지 정하려하고 현재 높이차가 j일 때 두개의 높이중 큰 값이라고 정의하자. 상태전이는 3가지이다. 1. i번 블록을 선택하지.. 2022. 8. 2.
백준 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.

티스토리툴바