백준 (223) 썸네일형 리스트형 [ICPC] 백준 2135 - 문자열 압축하기 www.acmicpc.net/problem/2135 다음 dp테이블을 정의한다. dp[i][j] := i번째부터 j번째까지 부분 문자열을 압축한 길이 문자열을 얼마나 압축이 가능한지 파악하기 위해 문자열을 압축할 구간의 길이에 대해 반복문을 돌린다. 문자열을 압축할 수 있는 모든 경우를 탐색하기 위해 해당 길이의 진약수를 모두 구하여 저장한다. 이 진약수들에 대해 반복문을 돌려 구간 내 문자열들이 진약수를 길이로 가지는 부분 문자열들로 압축이 가능한지 확인한다. 예를 들어 길이가 8인 "gogogogo"를 압축한다고 하고 8의 진약수 중 2에 대해 계산하면 "gogogogo"에서 길이 2의 부분 문자열은 "go"가 되므로 부분 문자열로 압축할 수 있음을 확인할 수 있다. 만약 압축이 가능하면 부분 문자열.. [COCI] 백준 3020 - 개똥벌레 icpc.me/3020 종유석과 석순을 살펴보면 어떤 식으로 나열되어 있든 부숴야 될 갯수에는 변함이 없다는 것이다. 그 즉슨 종유석과 석순을 정렬하고 이진 탐색을 통해 어떤 높이에서 몇개 부숴야 하는지 확인하면 빠르게 풀 수 있음을 알 수 있다. 1부터 h까지 반복문을 돌려 해당 높이에서 최소한으로 부술 수 있는지, 최소한으로 부술 수 있는 경우가 몇개인지 확인하면 AC를 받을 수 있다. 시간복잡도 $O(HlogN)$ 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include using namespace std; int n, h; int br.. 백준 1754 - 진영 순열 icpc.me/1754 A[0]이 입력으로 주어진 이유 $A[0] \geq 0$ 인 순열들에 대해 진영 순열로 변환하면 다음과 같은 모양새를 띠게 된다. 0 _ _ _ ... / _ 0 _ _ ... / _ _ 0 _ ... / _ _ _ 0 ... 그러면 a + b = c라고 할 때 c-진영 순열이 되는 경우의 수는 0 왼쪽에 있는 순열이 a - 1 진영 순열인 경우 * 0 오른쪽에 있는 순열이 b-진영 순열인 경우 여기서 0 왼쪽에 있는 순열은 0때문에 기존 진영 순열에서 1 더해지므로 a - 1 진영 순열이어야 한다. A[0]인 경우도 따로 처리해야 한다. 이럴 때는 길이 n의 수열이 c-진영 순열인 경우를 구하면 된다. 진영 순열 구하기 기존에 순열에서 확장하는 것을 생각해보자. 다음 대소 관계를.. 백준 1146 - 지그재그 서기 지그재그 순열로 배치하는 경우의 수를 구하는 문제이다. 모듈러 연산에 유의하면서 경우의 수를 구하는 점화식을 구현하자. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include #define mod 1000000 using namespace std; using ll = long long; int n; int euler[101][101]; int zigzag(int n, int k); int main() { memset(euler, -1, sizeof euler); euler[0][0] = 1; .. [ICPC] 백준 3948 - 홍준이의 친위대 icpc.me/3948 문제를 해석하면 홍준이는 지그재그 순열 형태로 병사를 배치하고 싶어함을 알 수 있다. 각 TC 마다 n까지 지그재그 순열을 나열하는 경우의 수를 출력해주자. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include using namespace std; using ll = long long; ll euler[21][21]; ll zigzag(int n, int k); int main() { cin.tie(0); ios::sync_with_stdio(false); memset.. 이전 1 ··· 28 29 30 31 32 33 34 ··· 45 다음
