본문 바로가기

PS87

백준 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.
백준 3830 / C++ https://www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net [ 풀이 ] 오프라인 쿼리로 계산해주면 쉽다. unkown은 미리 처리해주는것에 유의하자. 거리를 그래프에 담은 후 dfs로 순회하면서 연결된 것끼리 거리를 전처리해주고 차이를 구하면 된다. [ Code ] #include using namespace std; using ll = long long; const int MAX = 100010; ll n, m, a, b, .. 2022. 8. 12.

티스토리툴바