알고리즘90 CSES PS - Coin combinations (DP) https://cses.fi/problemset/task/1636 점화식 만들기가 쉽지 않다. https://www.youtube.com/watch?v=DJ4a7cmjZY0 영상설명.. 서로 다른 동전의 가치가 최대 100개 주어질때, 이 동전을 이용해서 정확하게 x원을 사용하는 경우의 수를 구해라. (단, 예를들어, 2 2 2 5와 5 2 2 2 는 같은 경우로 친다) 위에서 든 예시와 같은 경우가 생기지 않도록 동전의 순서를 강제해야 한다. f(k, i) = k원을 만드는데 0~i번째 동전을 순서대로 사용해서 만드는 경우의 수. = f(k-a[i], i) + f(k, i-1) ... ->마지막으로 i번째 동전을 사용하거나, 사용하지 않거나 예제로 dp 테이블을 채워보면 다음과 같다. 테이블이 채워지는.. 2020. 1. 16. CSES PS - nearest smaller values(NSV) https://cses.fi/problemset/task/1645/ 하나의 새로운 알고리즘, O(n) 카르테시안 트리라는 자료구조 구현의 기본 아이디어라고 함. https://wcipeg.com/wiki/All_nearest_smaller_values 영어설명 monotonic stack이라고도 함. https://www.acmicpc.net/problem/17298 다른 기본문제 최대 2e5개의 숫자를 입력받으면서, 처음부터 입력받은 그 시점까지 입력받은 숫자보다 작은 수 중에 가장 가까운 값의 인덱스를 반환하라. 1. k> n; stack s; s.push(0); for (int i = 1; i > a[i]; //입력받은 배열의 값보다 큰 값들은 없애버림 while (a[s.top()] >= a[i].. 2020. 1. 16. CSES PS - Towers (그리디, sorting) https://cses.fi/problemset/task/1073 sorting and searching으로 분류된 것으로 볼때, 무작위 크기를 순서대로 multiset에 넣으면서 처리하는 것에 주목하라는 의미인 듯 하다. 큐브를 이용해서 타워를 쌓을 것이다. (큰 큐브 위에 작은 큐브를 올리거나, 새로운 타워의 기반으로 사용하거나) n개의 큐브의 크기가 주어질 때, 모든 큐브를 사용해서 만들 수 있는 타워의 최소개수를 구해라. (반드시 입력 순서대로 처리해야 한다.) i번째 큐브를 이용해서 타워를 쌓을 땐, 그보다 약간 큰 큐브 위에 두는 게 최적이다. int main() { FAST; int n; cin >> n; multiset st; while (n--) { int a; cin >> a; auto.. 2020. 1. 13. BOJ 5670 - 새로운 자판 (Trie) https://www.acmicpc.net/problem/5670 이정도까진 풀수 있어야 한다. 자동완성 기능이 있는 자판이 있다. abczx abcxx abcyy 가 등록되어 있다고 가정할 때, a를 자판에 누르는 순간 abc가 자동완성된다. 등록되어있는 단어들을 모두 입력하는데 자판을 누르는 회수의 총합을 전체 등록된 문자의 수로 나눈 것을 구하자. 등록된 문자를 모두 find하면서 각 문자를 쓰는데 눌러야하는 자판 횟수를 ll cntKey(char* key, bool isRoot, ll cnt) 라고 하자. main에서 호출, 출력하는 코드 ll sum = 0; for (int i = 0; i cntKey(w[i], 1, 0); printf("%.2lf\n".. 2020. 1. 9. 이전 1 2 3 4 5 6 7 8 ··· 23 다음
