백준 (223) 썸네일형 리스트형 백준 14437 - 준오는 심술쟁이!! https://www.acmicpc.net/problem/14437 주어진 문자열은 사실상 장식이고 꽤 어려운 동적 계획법 문제이다. 이 포스트에서는 1차원 테이블과 슬라이딩 윈도우를 결합한 방법을 소개한다. 다음 테이블 2개를 정의한다. dp_old(i) := 이전 인덱스 문자까지 총 i만큼의 숫자를 소진해서 문자열을 바꾸는 경우의 수 dp(i) := 현재 인덱스 문자까지 총 i만큼의 숫자를 소진해서 문자열을 바꾸는 경우의 수 이미 바꾼 문자는 다시는 바꿀 수 없으므로 이전 1~25만큼 바꿨을 때 문자열이 변하는 경우를 테이블에 반영하면서 전진하면 된다. 이때 처음 dp_old(0)은 공집합 1로 규정한다. 그리고 우리는 dp를 계산해야 되는데 문제의 k가 최대 25라는 조건이 있으므로 $dp(i) =.. 백준 14848 - 정수 게임 https://www.acmicpc.net/problem/14848 포함 배제의 원리를 이용해 집합에서 원소들을 지워나가는 문제이다. 단, 이 문제는 서로 배수 관계인 수가 있을 수 있으므로 원소들을 곱할 때 최소공배수를 계산해야 올바른 답을 얻을 수 있다. 전체 코드 더보기 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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma") .. [APIO] 백준 1150 - 백업 https://www.acmicpc.net/problem/1150 전개 언뜻 보면 가장 짧은 거리만 취하면 되는 그리디로 보인다. 하지만 문제의 예제에서는 가장 짧은 경우인 회사 2 - 회사 3을 선택하고 있지 않다. 만약 {2, 3}를 택하게 되면 {1, 2}와 {3, 4}를 쓰지 못하게 되고 여기서 괜찮은 경우가 있을 수 있으므로 완벽한 최적해를 찾을 수 없다. 이를 거꾸로 보면 {2, 3}을 포기하면 {1, 2}와 {3, 4}를 챙길 수 있다는 말이 된다. 우리는 여기서 다음과 같은 전략을 생각해볼 수 있다. 일단 값이 작은 쌍을 가져가되, 상황에 따라 해당 쌍을 버리고 옆의 두 쌍을 취하기 그러면 예제를 완벽히 설명할 수 있다. 1. 일단 {2, 3}을 가져간다. 그러면 한 쌍이 연결된다. 2. .. [KOI] 백준 21759 - 두 개의 팀 https://www.acmicpc.net/problem/21759 이 포스트에서는 문제 지문을 완벽히 이해했다고 가정하고 풀이를 설명한다. 꽤 까다로운 트리 DP이다. 기본적인 트리 DP만 해봤다면 상당히 애를 먹을 수도 있다. 우선 다음 3개의 테이블이 필요하다. dp1(i) := i가 팀장이 되어 팀을 구성했을 때 최대 점수 dp2(i) := i가 팀장일 때 i의 자식 노드들에 대해 dp1(i)에 속하지 않은 정점을 대상으로 팀을 구성했을 때 최대 점수 dp3(i) := i가 루트인 서브 트리가 가질 수 있는 최대 점수 각 테이블을 계산해보자. 1. dp1을 계산하는 것은 쉽다. dfs 재귀로 합 dp를 수행하면 된다. 이때 자식 노드의 dp1 값이 음수인 경우는 더하지 않는 게 최적이다. 2. 자.. 백준 2381 - 최대 거리 https://www.acmicpc.net/problem/2381 서론 이 문제에서 써야 하는 테크닉은 은근 Well-Known이라고 한다. 대회를 준비하는 사람이라면 한 번쯤 익혀둘 필요가 있다. 식 전개 서로 다른 두 점의 좌표를 각각 $(x_{i}, y_{i}), (x_{j}, y_{j})$라고 하자. 그러면 두 점의 맨해튼 거리는 $|x_{i} - x_{j}| + |y_{i} - y_{j}|$임은 너무나도 잘 알고 있다. 자 여기서 신기한 걸 해보자. 우리는 $max(|x_{i} - x_{j}| + |y_{i} - y_{j}|)$를 구할 건데 절댓값을 어떻게 없앨까? 절댓값을 없애기 위해 다음과 같은 전개가 가능하다. $max(|x_{i} - x_{j}| + |y_{i} + y_{j}|) = ma.. 이전 1 ··· 5 6 7 8 9 10 11 ··· 45 다음
