mintuchel mintuchel

우선 가장 적은 화살로 풍선을 맞추려면 최대한 위에서 쏴서 한 화살로 여러개의 풍선을 맞출 수 있도록 해야한다 즉 한 화살로 최대한 여러개를 맞춰 모든 풍선을 없애는 쪽으로 짜면 된다 맨 초반에는 그냥 정직하게 짰다. 당연히 시간초과 하고 보아하니 N은 1000000까지 가능해서 O(N^2) 코드로 시간초과가 당연하다 #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin >> N; list ballons; // 순서가 중요 int x; for (int i = 0; i > x; ballons.push_back(x)..

우선 양수만 생각해보자 주어진 양수로 가장 큰 수를 만들려면 가장 큰 놈 두 놈끼리 곱해준 걸 합친게 가장 큰 수이다. a < b < c < d 라 했을때 a < a+n < a+m < a+l 이라 할 수 있고 이 4개의 수 중 두 개의 수로 만들 수 있는 최대값은 (a+m)*(a+l) 이다. 모든 경우의 수에서 a*a 는 동일하게 나온다고 쳤을때 (m+l)*a + m*l 이 가장 큰 경우이기 때문. 따라서 내림차순으로 정렬하고 앞에서부터 2개씩 묶어주면된다 그럼 음수쪽을 보자 음수쪽은 음수*음수이면 양수이므로 가장 작은 음수 두 개끼리 곱해준걸 합친게 가장 큰 수이다. 여기서 만약 수가 남는 경우를 생각해봐야하는데 만약 음수 하나가 남으면 그건 어쩔 수 없이 더해주어야하는 상황인데 만약 0이 있으면 0이..

이번 알고리즘 기말고사 때 그리디 문제 한 문제를 못풀었다. 굉장히 전형적인 유형인 0-1 배낭문제였다. 사실 0-1 배낭문제는 그리디 문제가 아니다. DP로 풀어야하지만 나는 그리디로 풀려다 틀렸다. 너무 그래프만 판 느낌도 들고 그리디랑 DP를 외면한 기분이 들어 방학때 그리디랑 DP를 파볼 생각이다. 지금은 그리디랑 dp 유형이 구분 조차 안되는 심각한 상태. 우선 재배치하면 되는 상황은 a*N (a+1)*M 일 수 밖에 없다 전체컨테이너개수/칸개수 가 딱 나누어 떨어져서 a*N개로 끝날 수 도 있다 우선 몇 개가 a만큼 쌓아지고 몇 개가 a+1만큼 쌓아지는지 알아내야한다 이걸 알아냈으면 작은 칸에는 큰 칸에서 컨테이너를 옮겨야한다 이때 어느 칸에서 어느칸으로 옮기는지는 생각할 필요가 없다 옮겨야하..

우선 초콜릿 크기는 무조건 2의 거듭제곱으로 시작한다. 그리고 초콜릿을 자를때는 무조건 반으로 자른다. 따라서 자른 초콜릿이 1일때 빼고는 홀수가 나올 수 없다. 그래서 N이 홀수면 무조건 끝까지 잘라야한다. 이제 조금 애매한 것이 짝수이다. 애매한 경우는 이런 경우를 생각해볼 수 있다 만약 10일 예로 든다면 10 = 8 + 2 10 = 4 + 4 + 2 이렇게 두 가지 경우를 생각해볼 수 있다. 이 중 어느 것이 더 적게 초콜릿을 자르는 경우인지 알아야하는데 일단 2의 거듭제곱이 아닌 수이면 무조건 기존 크기를 절반으로 자른 것은 필요로 한다. 왜냐하면 10은 2의 거듭제곱인 8이랑 16 사이인데 10이 8보다는 크고 16을 2로 나누면 8이기 때문이다. 즉 2의 거듭제곱이 아닌 짝수인 N은 무조건 ..

전에도 말했다시피 그리디에는 우선순위 큐가 굉장히 많이 쓰인다. 우선순위큐의 특징이 그리디라는 문제유형의 상황에 적합하기 때문이다. 이 문제도 아래와 같이 구현유형을 푼다는 생각으로 풀 수 도 있지만 우선순위큐를 사용하는 방식으로 풀어봄 arr = list(map(int,input().split())) cnt = 0 # 다 담을때까지 while sum(arr)!=0 : bag = 5 for i in range(4,-1,-1) : # 물건이 존재하고 계속담기가능할때까지 while arr[i]>0 and bag-(i+1)>=0 : arr[i]-=1 bag-=(i+1) cnt+=1 print(cnt) [우선순위큐를 사용한 그리디 구현 방식] 1. 우선 5kg은 그리디 계산을 해줄 필요가 없다 왜냐하면 5kg은..

이 문제는 자료구조로 분류해도 되는 문제이다. 그리디에서 우선순위큐를 어떻게 사용하는지를 알려주는 문제이기 때문이다. 1. 먼저 이 문제는 절대로 이중for문으로 접근하면 안되는걸 알 수 있다 N> N; int start, end; for (int i = 0; i > start >> end; lecture.push_back(make_pair(start, end)); } sort(lecture.begin(), lecture.end()); pq.push(0); for (int i = 0; i < N; i++) { int fastest_end = pq.top(); if (fastest_end

우선 각각 최소 최소로 사는 경우가 가장 일반적인 답인데 예외케이스가 존재함 항상 그리디 풀때는 일단 전제조건을 찾고 막턴 케이스를 생각해줘야함 6의 나머지만큼을 그냥 패키지로 샀을때 더 저렴할 수도 있고 패키지를 안사고 그냥 전부 다 낱개로 샀을때 더 저렴할 수도 있음 그래서 그거 마지막에 비교 해주면 됨 참고로 마지막에 x y z해서 비교하는거 더 줄이는 방법없나 더러워보인다... #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; cin >> N >> M; int min_p, min_s; min_p = min_s = 1001; int p, s; for (int i = ..

이 문제는 두 방법으로 풀 수 있다. 1. 그리디 최대한 적게 == 5kg으로 최대한 많이 따라서 케이스는 5*A 3*B 5*A + 3*B -1 이렇게 4가지가 가능하다 따라서 N/5 부터 시작해서 0까지 돌면서 최적값을 찾으면 된다 N최대값이 5000이므로 최악의 경우에 1000번 돌기 때문에 1초안에 충분히 해결가능하다 2. dp min ( dp[i-3] + 1, dp[i-5] + 1) 둘 중 하나인데 신경써야할 부분이 -1일때이다 하지만 좀만 끄적이면 -1은 7을 마지막으로 안나오는걸 알 수 있다. 7+5인 12까지만 직접 때려넣고 나머지 5000까지 알아서 채우게 하면 된다 12까지 채우는 이유는 12까지는 min식으로 하면 답이 있어도 -1로 배정되기 때문 13부터는 13-5 해도 8이기 때문에..