데옴's 기록장

레이지 세그를 공부하던 중 만난 문제다.. 그냥 딱 보면 이게 뭐지 싶은 발상이 쉽지 않았다. 문제에는 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 우선 한번 단순하게 생각해 보자. 일단 올라가는 속도가 빠른 소부터 보낸다고 생각한다면 아주 틀린 것은 아니다. 하지만 만약 내려가는 소가 있지만 올라오는 소의 속도가 더 느리다면 내려가는 소가 다 내려간 후 공백이 생긴다. 이 내용을 토대로 생각해 보자, 올라오는 소와 관계없이 내려가는 소가 계속 존재한다면 시간 이득을 볼 수 있다. 이미 올라간 소가 내려올 때 올라오는 소의 속도가 더 느리면 결국엔 이 구간에서 총 걸리는 시간은 올라오는 소의 것이 된다. 결국 이 말은 내려오는 소의 속도가 느린 만큼 더 많은 소가 올라와서 정상에 대기할 수..

set 활용법을 몰라서 개고생한 문제.. 너무 힘들었다. 체감 티어 : G1 태그 : greedy, set 모든 행성을 효율적으로 정복하려면 어떻게 해야 할까? 일단 다음과 같은 행동을 취해볼 수 있다. 1. 인구수가 가장 작은 행성부터 정복해 mobilization을 한다. 2. 인구수가 많은 행성부터 정복해 mobilization을 한다. 1번 아이디어는 반례가 생긴다는 것을 몇번의 관찰로 알아낼 수 있다. 그럼 이제 2번 아이디어를 가지고 어떤 식으로 가져가야 할지 생각해 보자. 먼저 고려해야 할 것은 어떤 행성들에서 충원 할 것이냐이다. 이는 최소한의 횟수로 충원 해야 하기에 가장 중요한 부분이다. 일단 전체 행성들의 합들을 이용해 충원 할 행성들을 정해볼 수 있다. k 개의 우주선으로 정복할 수..

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

우연히 본 문제가 쉽게 관찰을 얻을 수 있어서 기분 좋게 구현을 해봤다. 결과는.. 참혹했다. 역시나 한번에 되지 않는 것인지 수많은 TLE가 나를 반겨주었다.. n log n 풀이가 안되는 줄 알았는데 그럴리가 없다고 생각해서 다시 구현해보니 그냥 구현미스였던거였..(나는 아무 생각이 없다ㅏㅏㅏㅏㅏㅏㅏㅏ) 그래도 많이 봤던 유형의 그리디가 섞여있는 문제여서 좋았(?)다 체감티어: G2 태그 : 그리디, 우선순위 큐 문제에서 3가지, i일에 얻는 주식의 양, 판매시 얻는 가치, i일에 팔 수 있는 최대 주식수가 주어진다. 일단 문제를 보자마자 알 수 있는 것은 주식을 '잘' 분배하는 문제라는 것이다. 분배방법은 우선순위 큐를 이용해 간단하게 판별할 수 있었다. 우선 i일에 얻는 주식의 양은 Xi, 주식의..