돌이 코딩하는 방

문제 태그 : https://www.acmicpc.net/problem/15134 ※ 내가 관찰로 푼 문제들 중 하나이다. 따라서 갑자기 생각난 아이디어와 노가다, 말도 안되는 관찰들로 풀이가 이루어 질 예정이다. ※ 2018 NEERC가 끝난 후 LOTUS와 함께 풀었다. 문제 소개 테스트 케이스 별로 a,b,c,d 숫자 4개가 주어진다. 총 구슬의 갯수 $n=2^a+2^b+2^c+2^d$이다. 이때 우리는 n개의 구슬인 1묶음을 1개의 구슬씩 n개의 그룹으로 나누어야 한다. 이때 한 번의 행동으로 다음과 같은 작업을 할 수 있다. - (A,B,C) 그룹의 크기가 A인 모든 그룹을 각각 크기가 B인 그룹과 C인 그룹으로 나눈다. (이때 $A=B+C$) 이때 그룹의 최대 크기가 1이 될때까지 걸리는 행동..

문제 태그 : https://www.acmicpc.net/problem/4008 문제 소개 특정 값 a,b,c와 N명의 전투원들의 전투력이 주어진다. 전투원들은 인접한 전투원들끼리 묶어 몇개의 그룹으로 나눌 것이다. 각 그룹의 조정된 전투력은 그 그룹에 속한 모든 전투원의 전투력의 합을 x라고 했을 때, $ax^{2}+bx+c$이다. 이때 가질 수 있는 그룹의 조정된 전투력의 합의 최댓값을 구하시오. 문제 풀이 이 문제를 딱 보자마다 떠오르는 생각은 DP이다. '인접한 것 끼리 묶는다'도 DP를 쓰기 굉장히 좋은 조건이며, 정확히 DP[i]=1부터 i 까지 로 문제를 해결했을 때의 값으로 정의하면 깔끔하게 해결될 것 처럼 보인다. 이를 통해 DP값에 대한 식을 세워보면 다음과 같이 나온다. $DP[i]=..

문제 태그 : https://www.acmicpc.net/problem/13263 문제 소개 나무를 모두 자르고 싶다. 나무 N개의 길이$a_{i}$가 주어지고 N개의 $b_{i}$가 주어진다. 나무 길이 1을 자를때마다 다시 충전을 해야한다. 이때 충전하는 비용은 지금까지 완벽히 자른 나무의 번호 중 가장 큰 번호의 $b_{i}$이다. 이때 $a_{1}=1$ 이고, $b_{N}=0$ 이며, $a_{i}$는 증가하고 $b_{i}$는 감소한다. 문제 풀이 제일 중요한 사실은 $b_{N}=0$이라는 것이다. N번 나무를 자르면 그 이후로는 드는 비용이 0이기 때문에 이 문제를 다르게 해석하면 N번 나무를 자르는데 얼마나 비용이 드는가? 이다. 한 번에 N번 나무를 자를지 중간에 비용을 감소 시킨후 자르는 것..

CHT란? Convex Hull Trick의 약자로 말 그대로 볼록껍질을 이용한 트릭이다. Why? DP 문제에서 왜 사용하게 되는 트릭일까? DP 관계식이 다음과 같이 나왔다고 생각하자. $DP[i]=\underset{j $ax+b$ When? "DP식들을 일차함수꼴로 표현하여 볼록껍질을 만들어 줌으로써 해결을 한다."를 다르게 말해보면, DP식들을 일차함수 꼴로 표현했을 때 볼록껍질이 나오지 않으면 사용할 수 없는 테크닉이라는 것이다. 볼록껍질일 조건은 맨 위의 식에서 $A[j]$의 단조성이다. 주로 최솟값을 뽑을 때에는 $A[j]$가 계속 감소하게 된다. How? 1. 값 구하기 왼쪽과 같이 DP식에 맞는 직선들이 있을때 우리는 연속한 두 직선의 교점을 구함으로써 각 직선이 담당하고 있는 부분을 알..

DP에서 쓰이는 테크닉들 중 처음으로 비트마스크(Bitmask)에 대해서 설명하려고 한다. 보통 DP 말고 다양한 곳에서 쓰이기도 하지만 이글에서는 DP에 쓰이는 방향으로 초점을 두고 진행할 예정이다. Bitmask란? Bitmasking 기법이라고도 불리며, Bit에다가 masking을 하는 것이다. 다시 말해 DP값의 중요한 요소중 한가지인 '상태'를 배열등이 아닌 한 개의 숫자로 표현하겠다는 것이다. 예를 들어 bool arr[4] 배열이 채워질 수 있는 모든 경우의 수를 0~15의 수에 대응을 시켜 표현 하겠다는 것이다. 언제 & 왜? Bit masking은 보통 제한이 굉장히 작으면서, 모든 경우를 다 표현하고 싶을 때 사용한다. 이때 비트를 사용하기 때문에 스케일은 당연히 지수 스케일이며, 어..

이번에 다양한 테스트 시즌, 입학 시즌 등등의 이유로 코딩(PS)를 시작하려고 하시는 분들이 꽤나 있을 것 같다. 그러한 분들, 이번 신입생들 등을 위해서 내가 그나마 도움을 줄 수 있는 부분인 DP에 대해서 이야기를 풀어나가 보려고 한다. 전체적으로 DP 문제들에 대한 소개, DP 문제란? DP 문제 푸는 법 등에 대해서는 이 글에서 자세히 말을 했었다. 좋은 글이니 DP 공부를 하려면 한 번 읽어보는 것을 추천한다. 이번 글에서는 DP를 공부하는 법/DP를 잘해지려면? 과 같은 주제에 대해서 다뤄보려고 한다. 0. DP란? DP 문제를 푸는 법 위에서도 언급을 했지만 이 글에서 상당부분 잘 말해주고 있으니 참고하면 될 것 같다. 1. DP 문제의 특징 1.1 아이디어 & 생각 > 구현 일정 수준까지는..

797이 들어간 문제로 ICPC 2019 Seoul G번인 이 문제를 선택했다. 문제 태그 : https://www.acmicpc.net/problem/17974 문제 소개 점 N개의 좌표와 색깔이 주어진다. 우리는 이 점들중 1개이상, 몇 개의 점들을 뽑아야 한다. 뽑힌 점들을 A그룹이라고 하자. 뽑히지 않은 점들을 B그룹이라고 하자. 이때 모든 B 그룹의 점들은 가장 가까운 A그룹의 점들에 색깔이 같은 점이 존재해야 한다. 이때 뽑을 수 있는 A그룹의 최소 크기를 구하시오. 문제 풀이 일단 수직선상에 점을 흩뿌려놓고 생각을 해보자. 가장 먼저 연속된 같은 색깔의 점들을 그룹으로 묶어야 한다. 이때 관찰을 할 수 있다. 한 그룹내에서 최소 1개이상의 점은 뽑아야한다. 한 그룹내에서 최대 2개의 점까지만..

문제 태그 : https://www.acmicpc.net/problem/15647 문제 소개 간선의 가중치가 있는 트리가 주어진다. 1번 노드 부터 N번 노드까지 각 노드에 대해서 다른 모든 노드에서 그 노드까지의 거리의 합을 출력하시오. 문제 풀이 처음에는 하나당 O(logN)에 구하는 방법을 생각했다. HLD나 centriod decomposition을 떠올렸지만, 잘 모르는 쪽이기 때문에 더 이상 풀이를 떠올릴 수 없었다. 분명히 centriod를 활용해 풀 수 있을 것 같긴하다. 그래서 전체를 O(N)으로 구하는 방식으로 바꾸었다. Tree DP를 이용하는 방식이다. F[i] = 내 서브트리의 노드들이 i번 노드까지 오는데 걸리는 거리의 합 cnt[i] = 내 버스트리의 노드 수 dp[i] = 내..

문제 태그 : https://www.acmicpc.net/problem/18292 문제 소개 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. 문제 풀이 숫자가 작고 인접한 칸을 고르지 않는다는 조건. Bit를 활용한 DP가 풀이로 바로 떠오른다. 한 줄에 대해서 0~2^m 까지를 고르는 경우를 모두 고려 해주면 된다. 각 숫자별로 켜져 있는 비트가 골라진 칸 이라고 생각하면 된다. dp[i][j][k]= i 번째 줄까지 j 개의 칸을 선택했으며, 마지막 (i번째) 줄 의 선택된 모양이 k일때 최댓값이다. 총 테이블의 크기는 O(NK 2^M)이고, ..

문제 태그 : https://www.acmicpc.net/problem/1006 앞에서 순서대로 푸는 사람들이 절망할만한 문제이다. 1000~1005 보단 확실히 난이도가 있다. 문제 설명 원형 2열로 배치된 2n 개의 칸을 최소 그룹의 갯수로 묶어야 한다. 그룹에는 조건이 있다. 최대 2개가 같은 그룹일 수 있으며, 배치 상에서 연속된 칸이어야 하고, 두 칸의 값의 합이 m을 넘지 않아야 한다. 2칸이 한 줄이고 n줄이 있다고 생각하면 된다. 문제 풀이 DP를 쓰고 싶은 느낌이 들었다. 어떤 줄까지 다 채우는데 사용된 최소 그룹의 갯수를 이용해 다음 줄까지 채우는데 사용된 최소 그룹의 갯수에 영향을 준다고 생각할 수 있기 때문이다. 하지만 문제가 있다. 어떤 칸을 채울 때에는 이전 칸을 완벽히 채운 상..