그냥 하는 노트와 메모장

* BOJ 1410 패턴의 개수[분류 : 다이나믹 프로그래밍, 비트셋] 1. [같은 길이의 패턴] 길이가 다른 패턴은 절대 같은 단어를 포함할 수 없다. 같은 길이끼리만 모아서 생각해보자. 2. [비트 셋] 집합의 크기가 아무리 커봐야 15이므로 비트 셋을 쓰기에 충분히 작다. 또 2^15의 배열의 크기로도 충분히 작음을 알 수 있다. 3. [다이나믹 구성] 1.에 있는 조건을 가져와서 같은 길이를 가지는 패턴들만 생각해보자. dp[p][s]=p위치에 있는 문자를 결정해야하고, 현재 겹치는 패턴의 집합이 s일 때, 일치하는 패턴의 수가 정확히 K인 경우의 수 p이전에 선택한 문자들이 모두 일치하는, 또는 문자 ?로 대체할 수 있었던 패턴들이 s 비트 셋에 담겨있다. 현 위치 p에서 문자 a-z를 선택하며..

* BOJ 1040 정수[분류 : 비트마스크, 다이나믹 프로그래밍] BOJ 3026 V(링크: https://www.acmicpc.net/problem/3026, 풀이 링크: https://coloredrabbit.tistory.com/110)을 먼저 풀 것을 권장합니다. [풀이] 1. [사용할 수 있는 숫자의 수는 K] 이것이 시사하는 바는 총 10개의 숫자 중 K개만을 선택하여 계산하겠단 소린데 경우의 수로 따지면 아무리 커봐야밖에 되지 않습니다. 2. [백트래킹이 안되는 이유] 뭐 당연하겠지만 K개 골라봤자, 수의 길이가 최대 18까지 올라갈 수 있고, 거기서 K^18 경우의 수가 나올 수 있으므로 시간이 모자랍니다. 3. [자리수 dp] 높은 자리에서 낮은 자리로 내려가며 N과 똑같은 자리수에 똑..

* BOJ 1176 섞기[분류 - 다이나믹 프로그래밍] [요약] 인접한 사람들의 키 차이가 K초과가 되도록 N명을 배치하는 방법의 수를 구하자 [풀이]1. 이미 i명이 조건에 맞게 서있다고 가정해보자. 이 상태에서 한명을 뒤에 추가하려고 한다. 이때 i명은 조건에 충족하게 이미 서있기 때문에, i명 배치에서 가장 뒤에 있는 사람과 추가할 사람의 관계를 따져 K초과가 될 수 있는지 확인하면 된다.2. 먼저 몇명이 이미 서 있을 때, 맨 뒤에 설 사람을 정한다.3. 다음으로 그 뒤에 누굴 세울지를 정해서 조건에 맞다면 경우의 수를 셈해주면 간단하게 해결할 수 있다. #include #include using namespace std; const int MAX_N = 16; int main() { int N,..