데옴's 기록장

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

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

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

레이지 세그를 공부하던 중 만난 문제다.. 그냥 딱 보면 이게 뭐지 싶은 발상이 쉽지 않았다. 문제에는 2가지 쿼리가 주어진다. 1 l r : $\sum_{i=l}^{r}A_i+i-l+1$ 을 한다. 2 x : $A_i$ 의 값을 출력한다. 문제에서 1번 쿼리를 하면 $\sum_{i=l}^{r}A_i+i-l+1$을 하기 때문에 일반적인 구간 합 구하기 방법으로는 찾기 힘들다. 그렇다면 어떤 방법을 사용해야 될까에 대해 고민해 봐야 되는데 여기서 누적합을 응용하면 문제가 단순하게 변한다. 여기 예제 1번을 보자 1 2 1 2 1 여기서 누적합은 앞에 저장된 수를 더하지만 이번엔 앞에 수로 빼보자 1 1 -1 1 -1 이 상태에서 누적합을 하면 다시 처음 상태로 복원되는 것을 확인할 수 있다. 그럼 이걸 가..

체감 난이도: 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차이가 난다면 인접한 수임을 ..

체감티어: 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

이번에도 그리디로 돌아왔다. 아마도 내 4번째 다이아 문제가 아닐까 한다... 지금까지 푼 다이아 문제 중 가장 어려웠던 것 같다. 가장 오랜 시간 고민하다가 결국 다른 방법을 찾아봐서 풀었던 기억이 난다. 체감 티어: D4 문제는 우리에게 단순한 것을 요구한다. 그저 k 개의 네트워크 케이블을 이용해 회사들을 연결하는데 가장 길이가 짧게 하는 것이다. 예제를 가지고 간단하게 살펴보자, 우선 0km부터 가장 가까운 회사부터 A, B, C, D, E라고 정의하겠다. A-B의 길이는 3-1=2km, B-C의 길이는 4-3=1km, C-D의 길이는 6-4=2km, D-E의 길이는 12-6=6km이다. 여기서 가장 길이가 짧게 가져갈 수 있는 방법은 A-B와 C-D를 선택하는 것이다. 문제에서 말했듯 이미 회사..

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