Problem Solving/문제풀이 (45) 썸네일형 리스트형 [BOJ] 7579 앱 나는 사용가능한 최대 cost를 정해두고 0/1 knapsack을 돌리는걸 파라메트릭 서치로 해서 AC를 받았는데 보니까 아무도 이렇게 풀지 않았다 ㅠㅠ 억울해서 소스를 올린다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include using namespace std; int n,m;int arr[105];int cost[105];int cache[105][10005]; int dp(int idx, int remain){ if(idx==(n+1)) return 0; int& ret=cache[idx][remain]; if(ret!=-1) return ret; int ma=dp(id.. [BOJ] 2629 양팔저울 DP 정의는 $DP(i,j)$=i 이하 번호의 추를 사용하여 왼쪽 저울 - 오른쪽 저울의 무게가 j가 되게 할 수 있는가그러면 $DP(i,j)=DP(i+1,j+weight[i]) || DP(i+1,j-weight[i]) || DP(i+1,j)$라는 점화식이 세워짐. 왼쪽에 올리거나, 오른쪽에 올리거나, 아예 올리지 않거나. 간단한 DP problem 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include using namespace std; int f(int x){ return x+60000;} int n,m;int weight[35];int cache[35][120000]; int dp(in.. NYPC 예선 후기 세줄요약1. 머리나쁘고2. 게을러서3. 조짐 이번 NYPC 예선은 내가 공부를 엄청 게을리 하고 있다는 증거를 잔뜩 남겨두고 떠났다. 전체적으로 맞는 풀이인데 구현을 못하거나/반례가 있는 줄 알고 해결하지 못한 문제들이 너무 많았다. 해결하지 못한 문제는 16번 쉴드 생성기, 19번 종이접기, 21번 금 줄 게임, 22번 보라색 영역이다. 점수를 계산해보면 2,135점으로 본선 가기는 그른듯. 다음은 내가 해결한 문제들에 대한 간단한 해설과 소스코드이다. 3. 아이템 구매간단한 일차방정식을 해결하는 문제이다. Naive하게 코딩할 경우 시간복잡도는 선형으로 나온다. 확장 유클리드 알고리즘을 이용해서 로그 시간복잡도로 해결할 수 있을 것 같다는 느낌이 들긴 하는데 그렇게 코딩할 이유는 없으니까 ^^7 12.. [BOJ] 10840 구간 성분 진짜 어이없게 풀었다. 처음에는 해싱인지 모르고 $O(n^3)$에 최적화 생각했는데롤링 해시 구현하기 귀찮아서 그냥 알파벳에 숫자 하나씩 할당해 놓고 다 더한다음에 일치하면 okay라고 판별했다.int 범위 내에서 하니까 충돌나길래 long long 범위까지 늘렸더니 어셉됐다 ㅋㅋㅋㅋㅋㅋ결과적으로는 $O(n^2 lg n) 풀이임. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #include using namespace std; typedef long long ll; ll prime[]={1553543355441,683.. [BOJ] 2472 체인점 굉장한 학생 문제랑 다익스트라의 짬뽕이다. 덕분에 코드가 장난아니게 길다.각 정점이 최대 5개의 간선을 가지니 다익스트라의 $O(ElgV)$ 시간복잡도가 $O(VlgV)$로 바뀐다. 그러면 주어진 세 정점에 대해서 다익스트라를 한번씩 돌려볼 수 있고, 모든 정점에 대해 주어진 세 정점으로부터 각 정점으로부터의 거리 $dist_i$가 나오게 된다. 거리의 범위는 크지만 대소관계만을 비교하면 되므로 등위를 정렬을 통해 다시 매겨주자. 그러면 굉장한 학생 문제처럼 모든 정점에 대해 체인점을 세울수 있음/없음을 판별할 수 있다. 그 이후 들어오는 쿼리는 $O(1)$에 처리 가능하다. 수행 시간은 다익스트라, 정렬, RMQ 등이 다 섞여서 결과적으로 $O(NlgN)$이다. 개인적으로 문제 자체도 굉장한 학생 문제.. [CF] Codeforces Round #464 (Div. 2) 이번 CF는 총 A~F의 6개 문제로 이루어져 있었다. ABCD 50분만에 다풀고 E 하려다가 도저히 못하겠어서 반쯤 던져놓고 있었는데 끝나기 2분 전에 B 해킹이 들어와서 11초 남기고 B번 마지막 서브미션해서 맞았다. 덕분에 점수도 개판되고 레이팅도 100오를거 50밖에 안올랐다. 그래도 D번을 10분만에 풀어내서 점수에 아아주 큰 타격은 안간듯. D번이 이렇게 쉬울 줄 알았으면 DABC 순서로 풀걸 그랬다. 다음은 내가 푼 문제에 대한 솔루션들.A. Love Triangle time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output As you could know .. [BOJ] 1504 특정한 최단 경로 문제: https://www.acmicpc.net/problem/1504 그냥 다익스트라 몇번 돌리면 된다. 어차피 두 정점을 반드시 지나야 하는 것이라면 시작점->1번->2번->종점 아니면 시작점->2번->1번->종점 2가지 방법 안에서 반드시 최단경로는 나오게 되어 있다. 난이도는 1.75/5. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #define INF (100000000) using namespace std; int n;vector lis[805]; vecto.. [BOJ] 1916 최소비용 구하기 문제: https://www.acmicpc.net/problem/1916 그냥 다익스트라 그 자체이다. 풀이를 설명할 필요가 있을까? 난이도는 1.5/5 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #define INF (2100000000) using namespace std; int main(){ int n,m,st,en; scanf("%d %d",&n,&m); priority_queue Q; vector lis(n+1,vector()); vector dist(n+1,INF); for(int i=0;idist[here]) continue; for(.. 이전 1 2 3 4 5 6 다음
