데옴's 기록장

아이디어만 있다면 풀 수 있다 이건가요? 내가 문제 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번 쿼리가 들어오면 연결된 정점들의 개수를 세어주기만 하면 된다. 정점들..

발상자체는 쉽다고 생각이 들 수 있지만 막상 보면 전혀 쉽지 않은 끔찍한 문제였다. 문제를 읽고 처음 든 생각은 "어? 되게 쉽네?? 이게 왜 다이아지?" 하는 생각이었지만.. 다이아는 다이아다. 이 문제를 풀고 얻은 교훈은 다이아는 그 이유가 다 있기 마련임을 알게 되었다. 먼저 로봇의 이동방식을 보자. 1. 로봇은 앞으로 이동하거나 뒤로 이동한다. 2. 로봇은 벽 위에 놓여있는 센서를 하나 또는 여러 개를 들고 이동할 수 있다. 이 두 가지 조건을 가지고 로봇의 전체적인 이동 과정을 그려보면 아래와 같음을 알 수 있다. 그렇다. 로봇을 최소한의 이동거리로 모든 센서를 배치하려면 어쩔 수 없이 위 그림과 같이 이동해야 한다. 1. 왼쪽구간에 센서가 식별하지 못하는 구역이 있으면 로봇은 센서를 가지러 이..

모든 i번째 수에 대하여 나머지 R이 되도록 하는 숫자를 구하는 문제이다. i번째 수를 M으로 나누었을때를 식으로 표현하면 다음과 같이 나타낼 수 있다. $N_i=MQ_i+R$ 첫번째 수와 두번째 수를 M으로 나눈 항등식으로 표현하면 아래와 같다. $N_1=MQ_1+R$ $N_2=MQ_2+R$ 두 수를 빼면 $N_1-N_2=(Q_1-Q_2)M$ 와 같이 나타낼 수 있다. 인접한 수들에 대해 전부 해보면 $N_1-N_2=(Q_1-Q_2)M$ $N_2-N_3=(Q_2-Q_3)M$ $N_3-N_4=(Q_3-Q_4)M$ $N_4-N_5=(Q_4-Q_5)M$ ... $N_{n-1}-N_n=(Q_{n-1}-Q_n)M$ 위 식을 토대로 인접한 두 수의 차의 GCD값이 구하고자 하는 M의 값임을 알 수 있다. 주어진 ..

숫자를 분해한 후 얻을 수 있는 숫자들의 곱을 최대화하는 문제이다. 당연하게도 많은 수를 곱하는것이 이득임은 쉽게 알 수 있다. 그럼 최대한 많은 수를 곱을 최대화하는 것이 관건이 된다. 1,2,3은 분해를 하지 않아야 최대이다. 4는 2+2로 분해할 수 있고 이는 최대이다. 5는 2+3으로 분해할 수 있다. 6은 3+3, 7은 3+2+2, 8은 3+3+2로 분해했을 때가 최대이다. 이제 알 수 있는 사실은 3을 가능한 많이 포함하는 것이 수를 분해했을 때 최대가 될 수 있는 것이다. 하지만 10과 같은 경우는 3+3+3+1로 나눠진다면 1로 곱하기 때문에 최대로 만들 수 없다. 3을 많이 넣으면서, 1이 포함되지 않도록 조절하면 답을 구할 수 있다.

k개의 소수들의 곱을 순서대로 나열할 때, n번째로 오는 숫자를 구하는 문제이다. 가장 단순하게 k개의 소수들로 만들 수 있는 숫자들을 만든다는 전략을 사용해 보자. i번째로 오는 수에 k개의 소수를 각각 곱하여 만들 수 있는 수를 우선순위큐에 넣어준다. 중복되는 경우가 있을 수 있기 때문에 하나의 경우만 있을 수 있도록 처리해 준다. 문제의 메모리가 적으므로 메모리 초과에 유의하자. 더보기 #define _CRT_SECURE_NO_WARNING #include #include #include #include using namespace std; using namespace __gnu_cxx; // utils #define fastio ios::sync_with_stdio(false);cin.tie(0)..

체감으로는 골드 4?정도로 느껴지는 우선순위큐를 잘 활용하는 법을 안다면 쉽게 구현할 수 있는 문제라고 생각한다. 문제를 꼼꼼히 읽으면 쉽게 접근법을 찾아낼 수 있다. 우선 요구사항을 정리하면 다음과 같다. 1. 계산대에 줄을 선 순서대로 고객이 들어온다. 2. 빨리 계산이 끝나는 계산대에 고객을 안내하고, 기다려야 하는 시간이 같다면 계산대 번호가 작은 순서대로 고객을 안내한다. 3. 계산이 끝나는 대로 고객이 나간다. 계산을 마친 고객이 여러 명이라면 계산대 번호가 큰 순서대로 나간다. 기본적으로 계산대에 사람이 있어야 하므로 처음 $min(k, n)$명에게 순서대로 계산대에 배정한다. 이제 계산이 가장 빨리 끝나는 계산대의 시간을 $t$라고 해보자, 다음 손님이 왔을 때 그 계산대에서 계산을 끝마치..