데옴's 기록장

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

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

문제 제목이 참... 좀 그렇다 ㅋㅋ 이 문제는 BOJ 1489와 같다. 솔직히 이게 왜 플레지.. 생각이 들 정도로 단순한 그리디로 해결된다는 사실이다. 구해야 하는 것은 이안이와 예환이가 점수내기를 하고 이안이가 얻을 수 있는 최대 이익이다. 비교하기 쉽게 일단 정렬을 해보자. 이안이가 가장 최적의 효율로 내기에서 이기기 위해선 점수차가 최소가 되면서 이기거나 비기는 것이 중요하다. 여기까지 느낌을 잡았다면 그 후는 구현만 하면 된다. n제한은 10000으로 $O(n^2)$ 알고리즘을 사용할 수 있다. 이안이가 최소한의 점수차로 이길 수 있는 모든 과목 -> 무승부가 가능한 모든 과목 -> 지는 모든 과목순으로 점수를 계산해 주면 된다. 더보기 struct team { int point; bool u..

혼자 사다리타기에 대한 다양한 방법으로 연구하며 시간을 보내다 만난 문제이다. 오랜 시간 연구했던 탓인지 상대적으로 쉽게 해결할 수 있었다. 사다리들이 배치되어 있고 꼭 필요한 사다리들만 출력하는 문제이다. 문제를 해결하기 앞서 사다리타기의 성질을 알아보자. 세로줄 사이에 사다리를 하나 놓으면 a,b는 서로 swap이 된다. 그렇다면 여기서 할 수 있는 발상은 매우 단순하다. 한번 이미 사다리를 타고 이동했을때의 모든 도착지점을 안다고 생각해보자. i번째 출발점에서 도착점으로 가기 위해서는 그 거리만큼 사다리가 필요하다. 여기서 중복되는 사다리들이 존재할 수 있는데 여기서는 교차점이라고 말하겠다. n개의 출발점에서 도착지점으로 이동하는 모습을 표현하면 결국 사다리는 중복됨으로 교차점이 발생하는 구간에서 ..

유명한 그리디의 스케줄링 문제이다. 발상이 떠오르지 않는다면 어려울 수 있는 그리디 문제이다. 그러나 한번 알아두면 평생 쓴다! 어떤 방법으로 강의들을 배정해야 최소한으로 필요한 강의실을 개수를 구할 수 있을까? 순서대로 계획을 짜보자 1. 빨리 시작하는 순으로 배정한다. 시작이 빠른 강의가 가장 늦게 끝나는 경우가 있음으로 사용하기 어렵다. 2. 강의 시간이 짧은 순서대로 배정한다. 강의 시간이 짧은 강의가 제일 나중에 나오게 되면 비효율적이다. 3. 적게 겹치는 강의부터 배정한다. 이 역시 쉽게 반례를 찾을 수 있다. 4. 빨리 끝나는 순으로 배정한다. 뭔 짓을 해도 반례를 찾을 수 없다. 전략이 나왔다. 빨리 끝나는 순으로 강의를 배정시켜 보자. 이는 우선순위큐를 이용해 배정할 수 있다. 빠른 순으..

체감 난이도: D5 태그: 그리디, 정렬, 우선순위 큐 문제 요약: 최소 개수의 강의실을 사용해 모든 강의를 진행하게 한다. (단 1번 강의와 2번 강의는 같은 강의실에 배정하면 안 된다.) 강의실 배정의 상위 버전 문제이다. 우선 평범하게 강의실 배정을 하는 로직을 기반으로 생각 해보자. 만약 가장 빨리 끝나는 강의실에 1번 또는 2번 강의가 있는데 2번 또는 1번 강의가 들어온다면 다음으로 빨리 끝나는 강의실에 배정하는 식으로 진행시켜보자. 아래와 같은 상황이 들어오면 어떨까? 더보기 7 1 2 6 8 1 2 2 4 3 5 4 6 5 7 강의실 배정을 조금 변형한 방법으로는 이 상황을 해결할 수 없다. 위 상황을 조금 보기 쉽게 정렬해보면 아래와 같다. 더보기 1 2 (1) 1 2 (3) 2 4 (4..

사실 이 문제를 풀때 1624번을 푼다는 전제 하에 풀어보았지만... 1624는 다른 접근 방식으로 풀었다.. 이 문제는 생각보다 단순한 발상을 가지고 풀 수 있었다. 우선 최소한의 덱을 생성해 수열을 정렬된 상태로 만드는 것이 목표이다. 그렇다면 한가지를 떠올려볼 수 있다. 이미 정렬된 상태의 수열과 비교를 하며 덱에 추가할지 말지를 판별해볼 수 있지 않을까? 순서대로 덱에 집어넣어보며 정렬된 수열과 확인하는 방법으로 이 문제를 해결 할 수 있다. 처음에 무조건 덱이 하나 이상 있어야 함으로 덱에는 첫 번째 수가 있고 나머지를 순서대로 넣을지 말지를 정해본다. 현재 만들어진 모든 덱을 전부 둘러보며 j번째 덱에서 front와 back의 인덱스값과 i번째 수의 인덱스 값이 1차이가 난다면 인접한 수임을 ..

역시 우사코 문제는 정말 좋은 것 같다. 그리디 문제가 다 그렇듯(?) 아이디어 떠올리는 것은 좀 힘들었다. 체감 티어: P2 태그: greedy, sorting 우선 한번 단순하게 생각해 보자. 일단 올라가는 속도가 빠른 소부터 보낸다고 생각한다면 아주 틀린 것은 아니다. 하지만 만약 내려가는 소가 있지만 올라오는 소의 속도가 더 느리다면 내려가는 소가 다 내려간 후 공백이 생긴다. 이 내용을 토대로 생각해 보자, 올라오는 소와 관계없이 내려가는 소가 계속 존재한다면 시간 이득을 볼 수 있다. 이미 올라간 소가 내려올 때 올라오는 소의 속도가 더 느리면 결국엔 이 구간에서 총 걸리는 시간은 올라오는 소의 것이 된다. 결국 이 말은 내려오는 소의 속도가 느린 만큼 더 많은 소가 올라와서 정상에 대기할 수..

체감 티어:P3 태그:우선순위 큐, 정렬, 그리디 파머 존의 쿠폰을 뺏어가면 되는거 아닌가요 우선 파머 존에게 k 개의 쿠폰과 돈 m이 있다. 파머 존은 많은 소를 사고 싶어 하므로 최적의 방법으로 소를 살 수 있게 도와주면 된다. i 번째 소를 구입하려면 원가 Pi 또는 쿠폰 할인가 Ci를 지불해야 한다. 1. 쿠폰 할인가가 싼 소부터 쿠폰을 쓰는 것이 좋다 당연한 얘기이다. 하지만 원가를 지불하고 다른 소를 사는 것이 이득일 수 있다. 2. 쿠폰을 다른 소에게 쓰는 경우가 있을 수 있다 우리는 이것을 우선순위 큐를 통해 쿠폰을 쓸 필요가 없는 소를 찾을 수 있다! k 개의 쿠폰을 전부 사용해 쿠폰을 쓸 예정인 소 목록을 만들자. 이제 남은 소들을 보며 현재 Pi 원과 이전의 소를 쿠폰 없이 사고 Ci..