반응형 그리디16 백준 2109번 순회강연 - C++ 풀이 1. 시간 역순으로 매일 가장 강연료를 많이 받을 수 있는 강연을 고른다. 1. 시간 역순으로 매일 가장 강연료를 많이 받을 수 있는 강연을 고른다. 1781번 컵라면 문제와 동일한 문제이다. 13904번 과제 문제와도 동일하다. 1781번 게시글에 그리디 알고리즘에 관해 그림과 함께 설명해두었으니 참고. (강연료 = 컵라면이라고 생각하면 된다.) 백준 1781번 컵라면 - C++(cpp) 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있 please-amend.tistory.com #include #include #include usi.. 2022. 8. 24. 백준 13904번 과제 - C++ 풀이 1. 시간 역순으로 매일 가장 점수를 많이 받을 수 있는 과제를 고른다. 1. 시간 역순으로 매일 가장 점수를 많이 받을 수 있는 과제를 고른다. 1781번 컵라면 문제와 동일한 문제이다. 1781번 게시글에 그리디 알고리즘에 관해 그림과 함께 설명해두었으니 참고. (점수=컵라면이라고 생각하면 된다.) 백준 1781번 컵라면 - C++(cpp) 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있 please-amend.tistory.com #include #include using namespace std; typedef pair pii;.. 2022. 8. 22. 백준 1781번 컵라면 - C++ 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있는 문제는 데드라인이 day 이상인 문제들이다. 따라서 N일에 풀 수 있는 문제는 데드라인이 N인 문제들 밖에 없으므로, 그 중에서 가장 컵라면을 많이 주는 문제를 골라야 한다. (N-1)일에는 데드라인이 (N-1)일이거나 N일인 문제들을 풀 수 있다. 데드라인이 N일인 문제 중 가장 많은 컵라면을 주는 문제는 N일에 풀어야 하기 때문에, 이제 그 문제를 제외한 문제들 중에서 가장 많은 컵라면을 주는 문제를 고르면 된다. 같은 방식으로 N-2, N-3, ..., 1일까지 계속해서 가능한 문제 중 가장 많은 컵.. 2022. 7. 7. 백준 1285번 동전 뒤집기 - C++ 풀이 1. 각 행을 뒤집을지 여부를 고정한다. 2. 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 그리디 하게 정한다. 1. 각 행을 뒤집을지 여부를 고정한다. 행이 최대 20개, 열이 최대 20개이므로 각 행과 열에 대해 뒤집을지 말지 여부를 결정하는 경우의 수는 2^40가지이다. 따라서 브루트 포스로는 시간 내에 해결할 수 없다. 먼저 행에 대해서만 뒤집을지 여부를 결정해주자. 경우의 수는 2^20가지로 줄어든다. 2. 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 그리디하게 정한다. 행을 뒤집을지 말지 여부를 결정하고 나면, 이제 각 열의 뒤집을지 말지 여부는 그리디 하게 정할 수 있게 된다. 각 열끼리는 서로 영향을 미치지 않으므로, 각 열에 대해 뒤집는 경우와 뒤집지 않는.. 2022. 6. 28. 백준 25287번 순열 정렬 - C++ 풀이 1. 앞에서부터 시작하여 이전 수보다 크거나 같으면서 최대한 작은 수로 채워나간다. 1. 앞에서부터 시작하여 이전 수보다 크거나 같으면서 최대한 작은 수로 채워나간다. 감소하지 않으려면 앞에 있는 수를 최대한 작게 만드는 것이 최적이다. 앞(왼쪽)부터 차례로 i와 N-i+1 중에서 더 작은 수로 채워나가면 된다. 단, 감소하지 않아야 하므로 이전 수보다는 크거나 같아야 한다. 만약 i와 N-i+1 모두 이전 수보다 작다면 감소하지 않도록 만드는 것이 불가능한 경우이다. #include #include using namespace std; bool check(vector& A) { int N = A.size(); for (int i=0; i> T; while (T--) { int N; cin >> N; v.. 2022. 6. 10. 이전 1 2 3 4 다음 반응형
