데옴's 기록장

무작위화가 정해..? 오름차순 정렬을 통해 인원이 가장 적은 k개의 마을은 고려하지 말자. 인원이 가장 적은 k개의 마을을 다른 도시에 넣는다고 더 좋은 결과를 보장하지 않음을 알 수 있기 때문에 남은 2k개의 마을에서 적절히 선거구를 나누는 방법을 사용하자. 선거구를 나누는 방법으로 무작위화를 사용하면 된다.두 그룹으로 나눴을때 두 그룹 다 k*500을 만족하지 않는다면 계속 랜덤으로 배열을 섞어주는 방법을 사용하자. 이 방법이 왜 될까?? 는 잘 모르겠고 제한이 작고 문제의 조건을 만족하는 배치가 꽤나 많이 존재하기 때문에 충분히 시간안에 높은 확률로 답을 구할 수 있음을 보장할 수 있다.  신기한 문제

실력 상승을 위해 골드 5~3 랜디를 해보았다. 효과는 있는 거 같기도..대충 어디가서 꿀리지 않을 정도로만 잘해지면 될 거 같다.BOJ 2024 - 선분덮기 태그: 스위핑, 그리디 현재 정점을 덮을 수 있는 선분 중 왼쪽으로 가장 길게 뻗은 선분을 선택하면 된다.0번 정점부터 시작해 이동하며 갱신해 준다. 범위 잘못 잡아서 많이 틀렸던..BOJ 23889 - 돌 굴러가유 태그: 그리디, 정렬 +누적합 간단하게 생각하면 쉽게 풀이를 얻을 수 있었다. 돌이 시작하는 지점들 사이의 합을 구해둔 뒤 그중 구간의 합이 가장 큰 k개를 선택해 주면 된다. BOJ 1633 - 최고의 팀 만들기 태그: dp 3차원 dp에서 반복문으로 테이블 전이 시키는 과정이 조금 힘들었다. dp의 길은 끝이 없고..dp테이블을 다..

그리디(?)적으로 생각했을 때 그냥 자기 자리로 찾아가는 녀석의 수를 줄이면 된다.문제가 원하는 것은 오름차순으로 정렬을 하는데 움직이는 학생의 수를 줄이는 것이므로 전체에서 오름차순으로 정렬되어 있는 최대 학생의 수를 빼면 된다는 것을 쉽게 알 수 있다. 즉 전체에서 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..

아이디어만 있다면 풀 수 있다 이건가요? 내가 문제 2개를 고르면 상대가 가장 자신 있는 문제 하나를 가져간 후 내가 남은 문제를 가져간다.'나'와 상대는 i 번째 문제에 대해 각각 Ai, Bi 만큼의 자신감 수치를 가지고 있다.내가 문제 2개를 고르지만 정작 문제의 선택권은 상대에게 있다.문제 2개를 적절하게 잘 고르면 최적의 상황을 얻을 수 있다는데.... 당장은 보이지 않는다.우선 문제의 선택권이 상대에게 있다는 것에 초점을 두고 Bi를 기준으로 정렬을 해보자.4 2 8 66 5 7 8  2 4 8 65 6 7 8 여기서 맨 뒤에 있는 문제는 무조건 상대가 가져가는 문제, 맨 앞의 문제는 무조건 내가 가져갈 수 있는 문제임을 알 수 있다.그럼 어떤 식으로 두 개의 문제를 골라야 자신감 수치를 최대화..

여행 갈 때 얼마나 효율적으로 돈을 사용할 수 있는지 생각을 해본 적은 따로 없던 것 같다.가끔 코딩 문제를 풀다 보면 이런 상황을 자주 마주치게 되는 거 같아 나름? 신선한 거 같기도 하고..아무튼 이번 문제는 티어에 맞는 난이도를 가지고 있는 것 같다.  문제 요약을 하자면 지내야 하는 호텔들의 수가 주어진다.각 호텔마다 Pi만큼의 돈을 내야한다.호텔에 한번 숙박하면 1개의 쿠폰을 주고 k 개의 쿠폰이 모이면 호텔을 한번 무료로 숙박할 수 있다.이때 사용해야 하는 최소 금액을 출력하는것이 문제가 원하는 것이다. 당연히 호텔에 숙박할 때마다 쿠폰 개수가 k보다 크면 사용하는 것이 이득이다.문제는 이 쿠폰을 어떤 호텔에서 사용하는것이 관건인 것이다.호텔에 사용할 쿠폰을 정하는것은 최소 힙를 이용해 판별해..

문제가 원하는 것은 마법사가 책을 자지 않고 다 읽을 수 있는지 판별해 주는 것이다.마법사는 책을 읽을 때 즐거움 ai 만큼 소모하고 다 읽으면 bi 만큼 즐거움을 얻는다. 관찰 1. 우선 ai ≤ bi인 책을 읽으면 읽기 전보다 즐거움이 감소하지 않는다. 따라서 이런 책만 읽을 때에는 ak가 작은 순서대로 읽으면 된다. 관찰 2. 다음으로 ai > bi인 경우이다. 이 경우 책을 읽을 때마다 즐거움이 감소한다. 따라서 책을 거꾸로 읽는 방법을 생각해 보면 되는데 이 경우에는 관찰 1번과 같은 방법을 사용하면 된다. 그렇기에 bi가 큰 순서대로 읽으면 된다. 이제 즐거움이 감소하지 않는, 이득이 되는 책을 전부 읽은 후 이득이 되지 않는 책을 읽으며즐거움이 0 밑으로 떨어지는지 확인하면 정답을 구할 ..

오랜만에 푼 재밌는 골드 그리디 문제였다.쉬운 문제여서 정신적 건강에 많이 도움이 되었다. 문제에 정점이 N개, 루트노드가 1인 트리가 주어진다.각 노드에는 가중치가 있고 i(1모든 리프노드는 자신의 부모노드보다 가중치의 크기가 작거나 같기 때문에 루트노드에서 인접한 노드들을 선택하는 상황이 가장 큰 이득을 볼 수 있게 만들 수 있다. 즉, 루트노드를 우선순위큐에 넣고, 그 루트노드에 연결된 노드들을 우선순위큐에 넣으면서 계속 관리하면 각 상황마다 얻을 수 있는 가치의 크기가 최대가 된다.  사실 그리디라기보다는 bfs에 가까운 문제였다.

그냥 문제가 너무 길다. 문제를 요약하자면 모든 정점들이 어느 한 정점으로 연결되어 있는 트리가 있고 두가지 쿼리가 주어진다. 1. 두 정점의 간선을 끊는다 2. 선택한 정점과 연결된 정점들의 개수를 센다. 일반적인 방법으로는 문제를 해결하기에는 어려워보인다. 1번 쿼리는 n-1개 들어오기 때문에 최종 상태에서는 모든 정점들이 서로 연결되어 있지 않음을 알 수 있다. 그러면 여기서 쿼리를 거꾸로 수행해보고 싶은 생각이 들 수 있다. 간선을 끊는 쿼리를 구현하는 것은 어려우므로 쿼리를 거꾸로 실행하게 되면 간선을 추가하는 쿼리로 바뀌게 된다! 여기서 바로 유니온 파인드를 사용할 수 있다. 1번 쿼리가 들어오면 두 정점을 유니온 하고 2번 쿼리가 들어오면 연결된 정점들의 개수를 세어주기만 하면 된다. 정점들..