전체 글188 백준 1086 / C++ https://www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net [ 풀이 ] N이 작고 순열의 각 원소의 순서가 중요하므로 비트DP로 순회하자. p1 p2 .... pn 순으로 간다고 하자. p1에서 p2로 갈 때 수는 p1*10^(p2의 길이)+p2 가 된다. p2의 길이는 최대 50이므로 단순 계산으론 안되고 미리 10^m (modk)를 전처리해놓으면 된다. p_i들 또한 k로 나눈 나머지만 중요하므로 순회하면서 모두 k로 나눈 나머지로 전처리해놓자. 이제 dp식을 세우자. dp[bit][v]는 .. 2022. 8. 4. 백준 15678 / C++ https://www.acmicpc.net/problem/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net [ 풀이 ] dp[j]=max(0, dp[k])+a[j] 이다. (단, k>=j-D , k qe || e > D; for (int i = 1; i > K[i]; ll ans = K[1]; upd(1, 1, n, 1, K[1]); for (int i = 2; i 2022. 8. 2. 백준 3114 / C++ https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net [ 풀이 ] dp[i][j]를 (i,j)까지 왔을 때 합의 최댓값이라 하자. dp[i][j]는 dp[i-1][j-1], dp[i-1][j], dp[i][j-1]에서 올 수 있다. 앞의 두 경우는 이전dp값에다 현재 (i,j)에서 위아래로 바나나와 사과개수를 더해주면 된다. 이미 각 열에 대한 바나나의 합과 사과의 합을 전처리해놓자. dp[i][j-1]에서 오는 경우는 만약 (i,j)가 사과였다면.. 2022. 8. 2. 백준 13555 / C++ https://www.acmicpc.net/problem/13555 13555번: 증가하는 부분 수열 길이가 N인 수열 A1, A2, ..., AN와 정수 K 주어진다. 이때, 수열 A의 부분 수열 중에서 길이가 K이면서 증가하는 부분 수열의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] naive하게 세워보자. dp[i][j]를 A1~Ai까지 길이 j인 증가 부분수열의 개수라고 하자. dp[i][j]=sum(dp[k][j-1])이 된다. (단, a[k] n >> k; for (int i = 1; i > a[i]; for (int i = 1; i 2022. 8. 2. 이전 1 ··· 38 39 40 41 42 43 44 ··· 47 다음