본문 바로가기

전체 글188

백준 11616 / C++ https://www.acmicpc.net/problem/11616 11616번: Digit Division We are given a sequence of n decimal digits. The sequence needs to be partitioned into one or more contiguous subsequences such that each subsequence, when interpreted as a decimal number, is divisible by a given integer m. Find the number of different suc www.acmicpc.net [ 풀이 ] 우선 짚고갈 것은 전체수가 m의 배수가 아니라면 m의 배수인 여러부분으로 분할할 수 없다. 이제 전체수.. 2022. 8. 12.
백준 12911 / C++ https://www.acmicpc.net/problem/12911 12911번: 좋아하는 배열 첫째 줄에 성관이가 좋아하는 배열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net [ 풀이 ] dp[i][j]를 길이 i이고 j로 끝나는 조건을 만족하는 개수라고 하자. 전체 경우의 수는 dp[N][1]+...+dp[N][K]가 된다. 문제조건의 여사건은 A가 B의 배수라는 것이다. 즉, 뒤로갈수록 앞의 약수가 되면 된다. WLOG 순서를 뒤집어서 뒤로 갈수록 앞의 배수가 되도록 해도 된다. dp[i+1][j]=dp[i][1]+....+dp[i][k]-sum(dp[i][u]) (u는 j의 배수) 임을 알 수 있다. S(i)=dp[i][1]+...+dp[i][k]라고 정.. 2022. 8. 12.
백준 25112 / C++ https://www.acmicpc.net/problem/25112 25112번: Single-track railway The first line specifies the number of stations, $n$. In the second line, $n - 1$ numbers are given, corresponding to the initial travel times between the adjacent stations (the $i$-th number is the travel time between stations $i$ and $i + 1$). The third www.acmicpc.net [ 풀이 ] 매번 업데이트하면서 min(S[n]-2*S[i])를 찾아주는 문제이다. 펜윅트리로 업데이트해주.. 2022. 8. 12.
백준 14860 / C++ https://www.acmicpc.net/problem/14860 14860번: GCD 곱 N과 M 이 주어졌을 때, GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구하는 프로그램을 작성하시오. www.acmicpc.net [ 풀이 ] 어려운 문제였다. 각 소인수마다 최대지수를 구해주면 되는데 구하는 과정이 어렵다. 2의 최대지수를 구해보자. 2의 최대지수를 구할 때 n/2 * m/2 가 짝수인 쌍의 개수이다. 이때, 4의 최대지수를 구할 땐 2의 최대지수를 구하는 과정에서 값이 1번 세졌다는 사실을 이용한다. 4=2.. 2022. 8. 12.

티스토리툴바