본문 바로가기
728x90

백준브실골/Greedy19

백준 25091, Chain Reactions 개요 문제 링크 골드 1, Greedy, DP, Tree 리프노드부터 아직 방문하지 않은 부모를 방문하며 구한 구간의 최댓값의 합의 최댓값 접근 요즘 코포가 완전히 박살이 나서 코포식 운영을 해보려고 한다. 쓰잘데기 없는 기하학 문제는 그만풀고 구글 코드잼같은 메이저 대회의 문제들을 풀면서 시간도 재보고 하려고 한다. 문제는 코포 연습하기 진짜 좋은 문제다. 스타일이 똑같다. 문제로 돌아오면, 참 괴상한 문제인데 핵심은 자신이 어떤 리프에 의해 init되느냐 하는 것이다. 2번 예시를 약간 변형해서 보자. 그림을 그려보면 이렇게 되는데, 각각 무엇을 통해 init이 되는 것이 최선인지 확인을 해보자. 우선 위 예시의 정답은 4,3,5,6 순으로 init하는 것이므로 210이 된다. 먼저 2를 보자. 2은.. 2023. 6. 22.
백준 16207, 직사각형 개요 문제 링크 골드 3, Greedy 최대 1차이 나는 두 개의 선분을 양 변으로 하는 직사각형의 넓이의 합의 최댓값 접근 전형적인 그리디 문제, 정렬을 한 뒤 차이가 1 이하이면 순서대로 변으로 사용해주면 되고, 오름차순 정렬 후 가로가 정의되어 있다면 정의된 가로와 곱해서 전체에 더해주고, 정의되어있지 않다면 가로로 정의해주면 된다. 이게 왜 되냐? 하면 우선 길이가 긴 변을 선택해야 하는 건 당연한데, 길이가 가장 긴 두 변을 선택하는 것이 왜 이득인지는 바로 알기 쉽지 않다. 아래의 상황을 가정해보자. a1 > a2 > a3 > a4 여기서 a1×a2+a3×a4가 a1×a4+a2×a3나 a1×a3+a2×a4보다 큰 지 알면 되는 건데, 얼핏 기억나는 건 경시에서 다루는 재배열 부등식이라는 개념을.. 2023. 5. 10.
백준 27192, Pick a Pair 개요 문제 링크 골드 3, String, Greedy N개의 문자열로 N/2개의 pair를 형성할 때 pair의 prefix의 최소 길이의 최댓값 접근 일단 문제의 핵심은 전체 pair들의 prefix를 생각할 필요가 없다는 것이다. Pair의 prefix의 최소 길이의 최댓값이라는 말라는 말이 엄청 헷갈릴텐데, 먼저 pair를 골라야 하고, 그 조합의 prefix 길이가 최대가 되도록한다고 천천히 생각하면 문제의 구조를 이해할 수 있다. Pair를 고르는 것이 핵심인데, 아래 상황들을 천천히 읽어보자. Pair를 고를 조건, 즉 최소 prefix의 길이가 최대가 되도록 고르는 조건을 생각하는 과정이 상당히 그리디해서 Greedy를 추가했다. 사실 pair의 구성에는 최적의 pair가 항상 존재한다. 그.. 2023. 5. 4.
백준 18513, 샘터 개요 문제 링크 골드 4, Greedy, Heap 매 순간 샘터와 가장 가깝게 집을 지을 때 샘터와의 거리의 합의 최솟값 구하기 접근 재미난 우선순위큐(pq) 문제. 그리디하게 풀 수 있다. BFS를 쓸 수도 있다는데 오래걸릴 것 같아서 시도해보지는 않았다. pq를 어떻게 쓰냐? 우선 각 샘터 사이의 구간을 저장하자. 각 샘터는 점수를 가지고 있다고 생각하자. 매 순간 점수가 낮은 구간에 집을 짓는 것이 최선이고, 집을 짓는 순간 점수와 구간의 길이가 변한다. 길이가 0인 구간에는 집을 지을 수 없다. 구간은 양 끝에도 존재하며, 양 끝 구간과 샘터사이 구간의 점수는 산출 방식이 다르다. 이렇게 네 가지만 생각해주면 크게 어렵지 않게 구현할 수 있다. 구조체를 선언하고, 대소 비교는 점수를 중심으로 해준.. 2023. 4. 5.
백준 14222, 배열과 연산 개요 문제 링크 골드 5, Greedy 배열에 K씩 더해서 1부터 N까지 구성 가능한지 여부 출력하기 접근 그리디한 인간이 되어보자. 우선 1부터 N까지의 수의 개수를 세어주는 것이 필요하다. 그리고 모든 수의 개수가 1이 되면 1을 출력해주면 된다. K를 더한다 라고 생각하기보다 자신보다 K작은 수를 하나 뺏어온다 생각하자. 만약 없다면? 2K작은 수를 뺏어온다. 이렇게 위에서부터 찾아보며 2번 이상 등장한 값이 있으면 뺏어오면 된다. 이게 왜 그리디한 최적이냐?하면 아래 예시를 보자. 7 1 1 2 3 3 5 5 7 -> 1 2 3 5 5 6 7 (X) -> 1 2 3 3 5 6 7 (O) 만약 6이 3을 뺏어서 6을 만들어 버리면 4가 가져올 것이 없다. 대신 5를 하나 뺏어와야 배열을 구성할 수 .. 2023. 2. 23.
백준 1036, 36진수 개요 문제 링크 골드 1, Greedy K개의 수를 Z로 전환해 만든 N개의 36진수의 합의 최댓값 구하기 접근 1339 와 매우 유사해 접근은 쉽게 할 수 있었다. 그런데 1339와 같은 방식으로 풀면 안된다. 1339의 방식은 자리수마다 count를 저장하고 큰 자리수의 count가 큰 문자에 대해 Z를 할당하는 것이다. 그런데 이렇게 풀면 주어진 예시부터 풀리지 않는다. 왜그럴까? 우선 1339번은 입력되는 수의 개수가 최대 10개이다. 그 말은 각자리수의 합이 carry를 한 자리를 초과해 넘겨줄 수 없다는 말이다. 9×10+1 = 91 -> 9가 최대 carry가 될 것이다. 그런데 이 문제는 입력이 50개가 들어와버린다. 만약 1의 자리에 Z가 50개가 들어와버리면 35×50 > 36×36이 .. 2023. 2. 20.
백준 7775, 최종 순위 개요 문제 링크 골드 3, Greedy n개의 수를 합이 p이고 상위 k개까지 서로 다른 수의 개수가 d가 되도록 비오름차순 출력하기 접근 밤에 잠이 안와서 풀었던 문제. 풀고나니 단순했지만 시행착오가 많았다. 우선 핵심은 d에 의해 결정된다. 만약 d가 2이다. 그러면 {p,0,0...} 으로 1등에 몰빵해주면 된다. 예시에서는 그렇게 하지 않아서 틀리는 경우가 많았다. 그렇다면 d가 3이면? {p-1,1,0..} 으로 2등에 1을 주고 나머지는 1등에 몰빵 해주면 된다. 핵심은 1등에 몰빵하는 것이다. d가 3이상이면 1등부터 {d-1,d-2,....,1,0,0,....} 으로 최소 합을 이용해 d가지를 만들어주고 만약 합이 남는다면 1등에 더해주면 된다. 합이 남지 않았다면 최소 합을 이용해 d가지.. 2023. 2. 19.
백준 2812, 크게 만들기 개요 문제 링크 골드 3, Greedy N자리 수에서 K개를 제외해 얻는 최댓값 접근 그리디한 인간이 되자. 우선 귀찮은 인간은 k개를 제외할지, n-k개를 선택할지 부터 선택할 것이다. 여기까지 한 5-10분 고민한 것 같고, 나는 n-k개를 선택하는 방법에 대해 생각하기로 했다. 어떻게 선택한다는거냐, 아래 예시를 보자. // n=10, k=4, 6개를 골라야 함. // 가장 큰 자리를 구하는 경우 4177252841 |---| 41772 중에 가장 큰 수를 고르면 된다. 왜냐? 1) 우선 첫번째 자리를 선택할 때 최소한 뒤에 5개의 수는 남겨놔야 한다. 두번째 자리는 4개, 세번째 자리는 3개... 이렇게 이어진다. 2) 최선의 선택은 가장 높은 자리수를 가장 큰 값으로 하는 것이다. 즉 그리디하게.. 2023. 2. 11.
백준 1132, 합 개요 문제 링크 골드 3, Greedy 알파벳마다 숫자를 할당해 변환한 수가 leading zero가 없을 때의 최대 합 구하기 접근 1339번 문제에서 조건이 하나 추가되고 N수가 많아진 경우이다. 아마 N이 더 커지면 그리디 이외의 방법으로는 해결할 수 없을듯? 1339와 마찬가지로 우선 각 알파벳의 고유값을 구한다. 고유값은 각 자리마다 알파벳이 발견되면 10^(자리수)를 더해준 값이다. 이유에 대해서는 1339번 풀이를 읽어보자. 사실 이 부분이 핵심이고, "고유값을 구한다" 라는 개념이 잘 잡혀있다면 접근이 크게 어렵지 않다. 다음으로 leading zero가 있으면 안된다. 그럼 조금 더 복잡해지는 것이, 알파벳마다 기존에 고유값 이외에 다른 값도 저장해야 하므로 구조체를 활용해야 한다. 저장.. 2023. 2. 11.
백준 1339, 단어 수학 개요 문제 링크 골드 4, Greedy 알파벳마다 숫자를 할당해 변환한 수의 최대 합 구하기 접근 그리디한 문제라고 한다면 무조건 가장 최적의 알파벳을 찾아 숫자를 할당해야 함. 그 기준을 찾는 과정이 어려운 것. 기준을 어떻게 찾나? 하면 우선 가장 높은 자리수의 수에 가장 큰수를 할당하는 것을 생각할 수 있음. ACCC -> 9888 BDD -> 766 // A에 높은 수를 할당하는 것이 가장 최선 위의 사례에서 당연히 A에 9를 할당하는 것이 최선임을 알 수 있다. 그럼 다음 수는? B와 C의 최대자리수가 100으로 같다. 만약 A에서 Z까지 for문을 돌리면 B부터 8을 할당할테니 최선이 아니다. 아 그럼 큰 자리수부터 비교해가면서 등장 횟수가 더 큰 경우가 발견되면 먼저 큰 수를 할당하면 되겠구.. 2023. 2. 11.
728x90

티스토리툴바