사실 이 문제는 백준 19580번 "마스크가 필요해"와 완전히 접근방법이 동일하다. viyoung.tistory.com/171 [백준 19580번] [그리디/ 우선순위 큐] 마스크가 필요해 문제를 보고 생각보다는 쉽게 그리디 문제임을 파악할 수 있다. 문제 조건을 잘 보면, 최대한 많은 시민이 마스크를 구매할 수 있도록 유도해야한다. 즉 상식적으로 이 워딩을 보면 모든 시민들 viyoung.tistory.com 왜냐하면, 9676번과 19580문제에서 가장 Tight하게 해당 value를 만족하는 것을 선택한다는 핵샘이 동일하기 때문이다. 이전 19580문제 해설에서 언급한 것처럼 책을 가질 수 있는 scope를 increasing order로 정렬하고, 책 또한 번호를 증가시켜가면서 책을 가질 수 있는..

잘 생각해보면, 주유할 수 있는 양이 무한대이므로 최소 가격으로 넣을 수 있을 때 최대한 많이 주유하는 것이 유리하다. 다만, 문제가 되는 지점이 현재까지의 최소 가격을 어느 상황까지 커버할 수 있는지가 미지수이다. 예를 들어 지역 1, 2, 3, 4를 방문하는 상황이라고 하자 지역 1에서 현재 기름을 3의 가격을 판매하고 있다고 하자. 일단 적어도 지역 2까지는 가야하므로 최소한 지역2까지 가는데 필요한 거리에 필요한 주유량은 구입해야 한다. 하지만, 그 이상의 거리까지 구매를 해야하는지 여부는 지역2의 기름 가격을 알아야 한다. 지역 2의 기름 가격보다 싸면, 지역 1에서 지역2에서 지역3까지 가는데 필요한 기름을 미리 구매하는 것이 더 유리하다. 즉, 지역 2에서 3으로 갈 때 사용되는 기름의 가격..

사실 잘 생각해보면, 작은 숫자들을 순차적으로 뽑아주면 된다. 우선순위 큐를 활용해주어도 괜찮고, 전체 쿼리의 업데이트가 없으므로 배열을 정렬해줘서 하나씩 탐색하는 방식으로 처리해주어도 무방하다. 다만 0이 여러개 등장할 수 있는 지점만 조심해주면 된다. (맨 앞자리가 0이 될 수 없으므로 2번째 자리 이후부터 0을 배치하면 된다. 즉 첫 자리는 0이 아닌 숫자를 무조건 배치하고 0을 고려해주면 된다.) #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; while(true){ int n; cin >> n; vector data; if(n..

일단 이 문제를 보고 DP의 대표적인 유형인 Napsack문제를 떠올릴 수 있으나 가방 1개 당 보석 1개만 챙길 수 있다는 점에서 해당 문제와 차이점을 보이고 있다. 처음 접근한 방법은 다음과 같다. 만약 무게를 감당할 수 있다면 무조건 무게를 큰 것을 우선적으로 고르는 것이 유리하므로, 무게를 큰 순서대로 배치하고 감당가능한 무게이면 챙기는 방식으로 진행하였다. 다만, 이런식으로 진행하게 되면 최악의 경우 각 가방에서 N개를 전체탐색해야하므로 O(NM)이 나와 시간초과가 나오게 된다. 근본적으로 시간 초과가 나는 이유가 각 가방에 대해서 보석을 전체 탐색을 하기 때문이다. 발상을 바꿔서 무게를 우선적으로 고려하면, 가방의 한계 무게를 넘지 않는 것 중 가격이 최대인 것을 골라주는 것으로 문제를 바꿔 ..

여러가지 샘플을 만들어가면서 최적해를 구해보면 1. 남는 플러그 자리가 있으면 들어간다. 2. 없는 경우 다시 등장하는 것이 이후인 것부터 뽑는다. 만약 다시 등장하지 않는 경우는 해당 값을 INF로 처리해서 최우선적으로 뽑으면 된다. 적당히 현재 어느 숫자가 플러그에 꽂혀있는지를 저장해두는 배열을 만들고 관리해주면 된다. 추가적으로 순차적으로 데이터가 들어오고, 앞에서부터 다음 자리의 크기 비교를 해야하는 상황이므로 큐 자료구조를 활용하면 쉽게 풀 수 있다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; #define INF 987654321 int main(void){ ..

일단 주유소를 거리가 작은 것부터 정렬하고 해당 주유소를 갈 수 있는지 체크해준다. 만약 해당 주유소를 갈 수 있는 연료가 남았다면 일단 통과해주고, 없다면 이전에 있는 주유소 중 연료를 최대한으로 공급할 수 있는 곳을 방문했다고 간주해주면 된다. 계속해서 거리가 증가하는 방향으로 이동하고 있는 상황이므로, 결과적으로 모든 주유소를 방문해야 한다. 즉 각 주유소를 통과할 수 있는 연료가 남아 있는지 여부만 지속적으로 Greedy하게 체크해줘도 된다. 이전 주유소를 통과했다면 이전까지 도착하는데에는 연료가 충분했다는 것이므로 현재 주유소를 통과할 만큼의 연료만 있으면 되기 때문이다. 다만, 최소한으로 멈춰야하므로 연료 주입량이 많은 주유소에서 멈추는 것이 가장 이득이다. 만약 연료를 공급받지 않은 이전 주..

일단 이 문제를 보고 Greedy property를 발견하는 것은 그리 어렵지 않다. 직관적으로 생각해보면 제일 합이 크기 위해서는 자릿수가 제일 큰 것부터 봐가면서 해당하는 알파벳의 숫자를 키워나가면 되기 때문이다. 다만, 이렇게 접근할 경우에 상당히 복잡하다. 계속해서 어떤 알파벳이 처리 되었는지를 확인해주어야 하고(물론 방문 배열을 통해 처리할 수 있지만, 다른 문자열의 크기도 동시에 고려해야한다는 점에서 복잡하다.), 같은 자릿수의 알파벳의 경우도 어느 숫자를 배치해야할지 바로 결정하지 못하는 경우가 존재하기 때문이다. 예를 들어 ABC, CAB 문자열이 주어졌다고 가정하자. 그러면 Greedy property에 의해 A와 C가 9이거나 8일 때 가장 optimized하다. 다만, 첫번째 자리만 ..

2개씩 묶어서 판단한다는 점에서 백준 13975번 파일 합치기 3이랑 비슷한 느낌이 드는 문제이다. (viyoung.tistory.com/174) [백준 13975번] [그리디] 파일 합치기 3 전형적인 그리디 문제이다. 일단, 문제를 보면 최소 비용을 계산하는 문제이므로 직관적으로 큰 것은 나중에 더하고 싶은 느낌이 든다. 이 지점에서 그리디 문제인지 의심해볼 수 있다. Greedy prop viyoung.tistory.com 사실 직관적으로 생각해보면 숫자가 크기 위해서는 양수 기준으로는 큰 숫자들은 곱해주는 것이 유리하다. 다만, 1, 1과 같이 곱한 값이 더한 값보다 더 작은 경우도 존재하므로 곱하기 전에 더한 숫자보다 더 큰 지 여부만 체크해주면 된다. 문제가 되는 지점은 음수인데 음수의 경우도..