\(DP[N] : N\)번째 징검다리를 건널때 나올 수 있는 경우의 수 라고 잡아보면 \(DP[N] = DP[N-1]+DP[N-2]+...+DP[1]\) 이라는 식이 나오는데 \(DP[N-1] = DP[N-2]+DP[N-3]+...+DP[1]\) \(DP[N-2] = DP[N-3]+DP[N-4]+...+DP[1]\) . . . \(DP[1] = 1\) 이제 \(DP[1]\) 부터 \(DP[n-1]\)을 \(DP[n]\) 의 식에 대입해 보면 \(DP[N] = 2^{1}(DP[N-2]+DP[N-3]+...+DP[1])=\) \(2^{2}(DP[N-3]+DP[N-4]+...+DP[1])\) \(= 2^{3}(DP[N-4]+DP[N-5]+...+DP[1])... =2^{N-2}DP[1]\) 가 나옵니다. DP..
알고리즘은 그리디 입니다. 일단 제일 가격이 낮은 숫자들로 최대한 채웁니다. 이때, 0 이 제일 싼 가격이면 그 다음으로 싼 가격의 숫자를 맨 앞에 놓고 그 뒤에 0을 쭉 붙입니다. 그러면 쓰고 남는 돈이 있는데 이 돈으로 최대한 큰 수로 바꿉니다. 각 숫자에 대해 몇개씩 살 수 있는지 나오는데 이 숫자들을 내림차순으로 나열하면 제일 큰 숫자를 만들 수 있습니다. 제가 쫌 코드를 드럽게 짜기 때문에 풀이 이해용으로만 보시기 바랍니다. #include using namespace std; typedef long long ll; int n,pl,End; ll k,x,co[15],ch[15],tmp[15]; struct Money { ll cost; int num; }a[15]; bool cmp(Money p..
오프라인 다이나믹 커넥티비티 알고리즘을 알아보자. Offline Dynamic Connectivity 는 간선 추가, 삭제를 오프라인으로 처리하는 문제에 쓰인다. 대표적으로 BOJ의 16911 = 16912 = 15316 r) return; if(rl 1; add(node*2,l,mid,rl,rr,x), add(node*2+1,mid+1,r,rl,rr,x); } void Rollback(int cntt) { for(int i = 1;i > n >> Q; for(int i = 1;i op >> x >> y; if(x > y) swap(x,y); if(op == 1) vis[i] = 1,LifeTime[{x,y}] = i,QueryIn[i] = {x,y}; else if(op == 2) vis[LifeTim..
- Total
- Today
- Yesterday
- BOJ
- 알고리즘 문제 풀이
- 1909
- 비요뜨 존맛
- gunwookim
- ABC
- 비요뜨
- 쿼리
- codeforces
- 앳코더
- 누적 합
- 세그먼트 트리
- PS
- 정렬
- 냄새 싫어
- DP
- AtCoder
- 오일러 경로
- combination
- hyper
- 하이퍼
- Rabin-Karp
- Offline Dynamic Connectivity
- Constructive
- 간단한 풀이
- 김춘배
- 스택
- 수열과 쿼리
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |