일단 주유소를 거리가 작은 것부터 정렬하고 해당 주유소를 갈 수 있는지 체크해준다. 만약 해당 주유소를 갈 수 있는 연료가 남았다면 일단 통과해주고, 없다면 이전에 있는 주유소 중 연료를 최대한으로 공급할 수 있는 곳을 방문했다고 간주해주면 된다. 계속해서 거리가 증가하는 방향으로 이동하고 있는 상황이므로, 결과적으로 모든 주유소를 방문해야 한다. 즉 각 주유소를 통과할 수 있는 연료가 남아 있는지 여부만 지속적으로 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과 같이 곱한 값이 더한 값보다 더 작은 경우도 존재하므로 곱하기 전에 더한 숫자보다 더 큰 지 여부만 체크해주면 된다. 문제가 되는 지점은 음수인데 음수의 경우도..

전형적인 그리디 문제이다. 일단, 문제를 보면 최소 비용을 계산하는 문제이므로 직관적으로 큰 것은 나중에 더하고 싶은 느낌이 든다. 이 지점에서 그리디 문제인지 의심해볼 수 있다. Greedy property를 증명하는 것은 생각보다 간단한데 결과적으로 n개의 element를 1개의 element로 만들기 위해서는 n - 1 번의 파일 합치기를 해야한다. 이때, Current status에서 가장 작은 element를 선택하는 것이 partially optimized하면서 globally optimized를 만족하게 된다. 이때, 계속해서 최소값을 불러와주는 작업을 거쳐야하므로 우선순위 큐 자료구조를 사용하면 된다. #include #define fastio ios_base::sync_with_stdio..

잘 생각해보면 최대한 큰 숫자들은 나중에 자르는 것이 유리하다. 왜냐하면 남아있는 숫자가 크면 클수록 곱해지는 것이 더 커지기 때문이다. 따라서 이 지점에서 정렬을 하고 작은 숫자들부터 choice하는 아이디어를 확보하면 된다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int main(void){ fastio; int n; cin >> n; vector data_store; int current_length = 0; for(int i = 0; i > temp; data_store.push_back(temp); current..

나누는 숫자들이 300, 60, 10이다. 다만, 이 숫자들은 배수 관계이므로 무조건 더 큰 것을 쓸 수 있으면 쓰는 것이 유리하다. 예를 들어 60 * 5나 10 * 30을 하는 것보다 300 1개 쓰는 것이 무조건 유리하다. 즉, 더 큰 단위로 표현할 수 있으면 무조건 해당하는 것부터 쓰는 것이 유리하다. 이 부분에서 그리디 문제임을 파악하면 된다. 쉽다 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int main(void){ fastio; int n; cin >> n; if(n % 10 != 0){ cout

문제를 보고 생각보다는 쉽게 그리디 문제임을 파악할 수 있다. 문제 조건을 잘 보면, 최대한 많은 시민이 마스크를 구매할 수 있도록 유도해야한다. 즉 상식적으로 이 워딩을 보면 모든 시민들이 구매할 수 있게끔 최적(?)의 방법으로 구매하는 것이 가장 이득이라는 것을 간파할 수 있다. 즉, 이 지점에서 그리디 문제가 아닐까 의심을 해볼 수 있다. 직관적으로 잘 생각해보면 마스크를 제일 많이 팔 수 있는 경우는 해당 마스크 가격에만 구매할 수 있는 사람을 최우선적으로 구매권을 주면 된다는 것을 간파할 수 있다. 즉, 이 문제를 풀기 위해서는 각 상점을 기준으로 해당 가격 마스크를 시민들의 구매할 수 있는지 여부를 체크하고 그 중 가장 최적의 케이스 순서대로 구매를 진행해야 한다. 다만, 이 문제에서 입력값이..

상황 자체는 쉽게 잡았으나, 구현에서 살짝 애를 먹었다. (사실 2시간 잔 상태로 기본 틀을 잡아서 몇번 더 틀렸다 ㅋㅋ) 일단 이 문제를 풀기 위해서 상황 자체를 바꿔가면서 상황을 이해하려 해야한다. 그러면 크게 3가지 상황으로 이 문제를 바라볼 수 있다. 1. 세로가 홀수인 경우 이 경우는 생각보다 매우 쉽다. ㄹ모양으로 계속해서 왼쪽, 오른쪽으로 타고 내려가면 된다. 구현 자체는 zero base로 짯다고 가정했을 때, 세로가 짝수이면 Right, 홀수이면 Left를 출력해주면 된다. 2. 세로가 짝수이나, 가로가 홀수인 경우 이 경우는 1번 케이스의 변형으로 사각형을 90도 돌렸다고 생각해보면 1번 케이스로 치환할 수 있다. 모양은 위 아래를 반복하면서 전체적으로 오른쪽으로 진행해주면 된다. 구현..