데옴'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 밑으로 떨어지는지 확인하면 정답을 구할 ..

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

숫자를 분해한 후 얻을 수 있는 숫자들의 곱을 최대화하는 문제이다. 당연하게도 많은 수를 곱하는것이 이득임은 쉽게 알 수 있다. 그럼 최대한 많은 수를 곱을 최대화하는 것이 관건이 된다. 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이 포함되지 않도록 조절하면 답을 구할 수 있다.

문제 제목이 참... 좀 그렇다 ㅋㅋ 이 문제는 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차이가 난다면 인접한 수임을 ..