hjhj97

[Codeforces 1140C]Playlist 문제 설명 : n개의 노래의 length와 beauty가 각각 주어진다. 나는 여기서 최대 k개의 노래를 선택해서 pleasure가 최대가 되도록 해야 하는데, pleasure를 계산하는 공식은 (선택한 노래들의 length들의 합)*(선택한 노래들 중에서 beauty가 가장 작은 값)으로 계산된다. 풀이 : 우선 beauty를 오름차순으로 정렬한다. 정렬을 하는 이유는 값을 크기 순으로 배치하여 한쪽 방향으로 순회함으로써 하한(lower bound)을 고정할 수 있기 때문이다. 문제에서 pleasure를 계산할 때 어차피 beauty가 가장 작은 값이 무엇인지만 중요하므로, 가장 작은 값을 미리 정해놓음으로써 나머지 노래들은 무조건 그 보다 beauty가..

1095C-Powers of Two 어떤 수 n이 주어지면 그 수를 총 k개의 2의 거듭제곱수(1,2,4,8...)의 합으로 표현할 수 있는지, 가능하다면 그 조합을 출력하는 문제이다. 콘테스트 당시에는 dfs를 이용해서 풀어보려고 했으나, n=10억, k=20만이기 때문에 당연히 시간이 터진다. 그래서 왠지 dp적인 기법이 섞으면 되지 않을까 고민하다가 결국은 못 풀었다. 결론부터 얘기하면 dp가 아닌 다른 방법으로도 풀 수 있다. 만약 이 문제에서 k가 최소가 되도록 하는 문제였다면 그나마 쉽게 생각할 수 있었을 것이다. k의 최소는 엄청나게 큰 2의 거듭제곱 수부터 시작해서 대소 비교를 하면서 n에서 그 값을 뺄 수 있으면 빼고 아니면 2로 나눠가는 (마치 LCA처럼) 기법을 쓰면 k의 최소값을 구..

[BOJ 1826] 연료 채우기​ 우선순위 큐(힙)를 이용해서 그리디로 푸는 문제이다. 우선 주유소를 거리 순으로 정렬한 뒤에, 현재 연료양을 가지고 최대한 갈 수 있는 범위 안에 속하는 주유소들의 연료 양(c)를 모두 최대 힙에 넣는다. 그 다음 힙의 top에서 원소(c)를 하나씩 빼보면서 이 연료를 주입했다면 다음 주유소까지 도달 할 수 있었는지를 확인한다. 만약 불가능 하다면 가능할 때까지 힙에서 원소를 계속 빼서 더해본다. 만약 모두 뺐는데도 다음 주유소까지 도달할 수 없다면 이는 불가능하다는 뜻이므로 -1을 출력하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 3..