데옴's 기록장

그리디(?)적으로 생각했을 때 그냥 자기 자리로 찾아가는 녀석의 수를 줄이면 된다.문제가 원하는 것은 오름차순으로 정렬을 하는데 움직이는 학생의 수를 줄이는 것이므로 전체에서 오름차순으로 정렬되어 있는 최대 학생의 수를 빼면 된다는 것을 쉽게 알 수 있다. 즉 전체에서 lis를 빼주면 된다.더보기int main() { fastio; int n; cin>>n; vectorarr(n); for(auto&v:arr)cin>>v; vectordp(n,0); int ans=0; for(int i=0; iarr[j])dp[i]=max(dp[i],dp[j]+1); } ans=max(ans,dp[i]); } cout

매우 쉽게 점화식이 나와서 기분이 좋았던 문제다. i일에 일을 받아서 작업을 하면 i+t[i]일에 p[i]원을 받는다.일을 받지 않고 다음날로 가는 경우에는 dp[i+1]=max(dp[i+1],dp[i])일을 받아서 하는 경우에는 dp[i+t[i]]=max(dp[i+t[i]],dp[i]+p[i]) n+1일까지 일을 할 수 있으므로 dp[n+1]이 구하고자 하는 값이다. 더보기int main() { fastio; int n; cin>>n; vector>arr(n); for(auto&[a,b]:arr)cin>>a>>b; vectordp(1500001,0); for(int i=1; i

더보기  dp가 어려운 나에게 실버 1 dp를 풀어보는것을 시도했다사실 어렵다기보다는 아이디어는 거의 나오는데 점화식을 못 세우는 기현상이 있었고 티어에 비해 기본기가 많이 부족한 거 같아서 시작.. 점화식 느낌 잡기 용으로 푼 4문제 정도 가볍게? 정리해본다.실버 dp였기는 했지만 이전에 구한 상태를 현재 구하고자 하는 값에 반영한다는 느낌을 가지고 문제를 보면 점화식이 쉽게 나왔다.BOJ 15645 - 내려가기 2 , BOJ 2096 - 내려가기내려가기 2를 풀면 내려가기를 풀 수 있다. 다음 칸으로 가는 경우는 바로 아래칸과 인접한 좌 우 칸으로 이동하는 것이다.그렇다면 i번째 줄에 j번 칸에 올 수 있는 최대 값은 max{i-1번째 줄에서 j번 칸으로 이동 가능한 칸}으로 볼 수 있다. 15645..

체감티어: G5 태그: 냅색, dp, 브루트포스 제 1회 임스의 메이플컵의 C번이다. 냅색은 구원자이다. 일단 n명중 m명을 뽑아 15분간 보스를 잡고 m명이 얻은 값을 최대화 하면 되는 간단한 문제이다. 뭔가 dp냄새가 난다. 하지만 테이블을 어떻게 잡아야 할지 잘 모르겠다. 일단 15분은 900초이므로 900칸의 배열을 생성하면 준비는 끝난다. 문제는 각 캐릭터마다 초당 데미지가 다르다. 하지만 보스의 체력과 초당 데미지 사이에 관계를 Wi로 보고, 보스를 잡고 주는 값을 Ci로 보면 단순한 냅색의 형태가 나온다. i번째 보스를 잡는데 걸리는 시간은 (보스의 체력 / 초당 데미지)의 올림으로 나타낼 수 있다. 이를 각 캐릭터마다 따로 적용하고 냅색을 한 결과의 합을 구하면 된다. 더보기 #define..

제1회 춘배컵에 나온 문제다. 춘배는 귀엽다!! 나비도 귀엽다!! 체감 티어 : G5 태그 : map, dp, recursion 문제가 정말 친절하다. A가 짝수면 /2, 홀수면 (A-1)/2, (A-1)/2+1로 분할해서 M을 만들 수 있는지 확인하는 문제이다. 간단한 재귀함수로 구현하면 ... int f(ll n, ll m){ if(n==m){ return 1; } if(n>n>>m; cout>m; f(n,m); cout