lv2 ) 완전범죄(틀림) 그리디 vs DP

https://school.programmers.co.kr/learn/courses/30/lessons/389480#

 

그리디로 접근 (실패)

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
using namespace std;

//다중조건: 1. 2번째 원소 오름차순  2. 1번째 원소 오름차순 

bool comp1(vector<int> v, vector<int> tar){
    if(v[0] != tar[0])
        return v[0] > tar[0]; // A 내림차순
    return v[1] < tar[1];     // A 같으면 B 오름차순
} // v == tar 인 경우 v <= tar  -> true 반환. 이는 comp(x, x) = true가 되어버림에 따른 sort 알고리즘 내부 규칙에 위반 됨. 그렇기에 v < tar로 하자.
bool comp2(vector<int> v, vector<int> tar){
    if(v[1]!=tar[1]){ // B흔적 내림차순
        return v[1] < tar[1];
    }
    //2. 만약 B의 흔적이 같다면 A의 흔적(idx 0) 오름차순정렬
    return v[0] < tar[0];
}


int solution(vector<vector<int>> info, int n, int m) {
    int suml = 0; // return
    int sumr = 0;
    
    int flag = 1;
    sort(info.begin(), info.end(), comp1); // 정렬
    
    for(int y = 0; y < info.size(); ++y){
            if(flag == 1){
                sumr+=info[y][1];
                if(sumr >= m){
                    sumr-=info[y][1];
                    suml+=info[y][0];
                    if(suml>=n){
                        suml = -1;
                        break;
                    }
                    flag = 0;
                }
            }
            else{
                suml+=info[y][0];
                if(suml>=n){
                    suml = -1;
                    break;
                }
            }
    }
    int suml2 = 0, sumr2 = 0;
    flag = 1;
    sort(info.begin(), info.end(), comp2); // 정렬
    for(int y = 0; y < info.size(); ++y){
        cout<<info[y][0]<<" "<<info[y][1]<<endl;
            if(flag == 1){
                sumr2+=info[y][1];
                if(sumr2 >= m){
                    sumr2-=info[y][1];
                    suml2+=info[y][0];
                    if(suml2>=n)
                    {
                        suml2 = -1;
                        break;
                    }
                    flag = 0;
                }
            }
            else{
                suml2+=info[y][0];
                if(suml2>=n){
                    suml2 = -1;
                    break;
                }
            }
    }
    if(suml == -1)return suml2;
    if(suml2 == -1)return suml;
    if(suml>suml2)return suml2;
    return suml;
}

 

 

이 코드의 전략은:

"B에게 계속 몰아주다가 B가 한계에 가까워지면 그때부터 A에게 준다"

근데 어떤 물건을 B에게 줄지가 중요한데, 정렬로는 그 최적 조합을 찾을 수 없다.

 

정렬 방식

comp1) 1: A 내림차순   2: B오름차순

comp2) 1: B 내림차순  2: A 오름차순

 

leftl 은 comp1 , leftl2는 comp2 방식 적용

둘다 -1이면 -1리턴, 그렇지 않으면 둘 중 작은 값 리턴

 

---

[그리디로는 안된다고 한다. 그런데 반례를 찾지 못했다.]

 

그리디 풀이는 이번 문제를 통과하지 못한다. 

A의 흔적의 개수가 작은 순서대로 정렬을 하고 선택했을 때 A의 최솟값이 나오지 않기 때문이다. 

 

(반례)

[1, 2], [2, 3], [3, 2] [4, 7]  n = 7 m = 8 가정

그리디로 풀게 되면 정답은 6이 된다 A의 흔적 개수가 6이 될 때 14 - 7 = 7 B의 흔적 개수가 7이 되어 통과되지만

정답은 A의 흔적 개수가 4일 때 14 - 7 = 7이 되어서 조건을 만족하여 4가 정답이다.

 

출처: https://20240228.tistory.com/435 [지적 겸손함:티스토리]

 

 

내 코드에서 반례 적용 시 

comp1 ) [4, 7], [3, 2], [2, 3], [1, 2]

comp2 ) [1, 2], [3, 2], [2, 3], [4, 7]

 

TC 답이 4나온다.(정답)

 

해당 블로그에서의 반례가 내 코드에선 틀렸다.

 

---

내 코드 반례

info = [[2,2],[3,2],[2,2],[1,1],[3,2]]
n = 9, m = 8
그리디: 3  →  정답: 2

 

최적 배정: A B B B B

• A가 [2,2] 훔침 → A흔적=2
• B가 나머지 4개 훔침 → B흔적=2+2+1+2=7 < 8 ✅

근데 그리디는 정렬 후 B흔적이 한계에 가까워질 때까지 B에게 몰아주다가 전환하는 방식이라, 첫 번째 물건을 A에게 줘야 최적이라는 걸 알 수가 없다.

즉 "어떤 특정 물건을 A에게 줄지" 를 정렬만으로 결정할 수 없는 게 본질적인 한계이다.

 

A에게 넘기는 물건	A흔적	B흔적
[2,2]	2	7 ✅
[3,2]	3	7 ✅
[2,2]	2	7 ✅
[1,1]	1	8 ❌
[3,2]	3	7 ✅

 

comp1) 1: A 내림차순   2: B오름차순

comp2) 1: B 내림차순  2: A 오름차순

두가지 정렬을 적용해서 둘 중 하나의 A값이 작으면 그 값을 리턴한다. 다만 그 작은 값이 -1이면 둘다 -1이 아니라는 가정 하에 큰 값을 리턴한다.

 

그러나 위와 같은 반례처럼 해당 조합(comp1, comp2 정렬 후 선택 전략)이라도, 즉 어떤 정렬 순서로도 ("정렬 기준을 2, 3개 ... 10개로 늘려도) "운 좋게 맞는 케이스"가 늘어날 뿐, 항상 최적을 보장하지 않는다.

최적을 항상 보장하려면 DP를 사용해야한다.

 

 

 

---

그리디 VS DP

그리디 ⊂ DP 관계

많은 경우 그리디로 해결 가능한 문제는 DP로도 해결 가능하다.
반면 DP로 해결 가능한 문제 중에는 그리디로 해결할 수 없는 문제도 많다.
따라서 실전에서는 DP가 그리디보다 더 범용적인 접근으로 여겨진다.

 

 

정확히는 다음과 같이 이해하는 것이 좋다.

• 그리디로 최적해가 보장되는 문제들은 대체로 DP적으로도 표현 가능하다. (그리디는 항상 “왜 최적인가”에 대한 증명이 중요하다.)
• 하지만 DP가 필요한 문제 중 상당수는 greedy choice property(탐욕 선택 성질)가 성립하지 않아 그리디로 해결할 수 없다.

예를 들면 다음과 같다.

그리디와 DP 모두 가능한 문제:

• 동전 문제(특정 화폐 체계)
• 활동 선택 문제
• 최소 신장 트리
• 최단 경로(비음수 가중치의 다익스트라)

DP는 가능하지만 그리디는 불가능한 대표 문제:

• 0/1 배낭 문제
• LIS 일반 DP
• 행렬 곱셈 순서
• 편집 거리

특히 0/1 배낭 문제는 대표적인 예시다.

• “가성비 좋은 물건부터 담자” 같은 단순 그리디는 반례가 존재한다.
• 하지만 DP는 항상 최적해를 구할 수 있다.

실전에서는 다음처럼 접근하는 경우가 많다.

• 그리디가 바로 보이지 않으면 DP를 먼저 고려하는 것이 안전한 경우가 많다.
• 그리디는 반드시 교환 논법(exchange argument), greedy choice property, 반례 검증 등을 통해 정당화해야 한다.
• 반면 DP는 상태 정의와 점화식만 올바르면 최적성을 구성하기 비교적 쉽다.
• 대신 시간과 메모리를 더 사용하는 경우가 많다.

또한 “DP는 느리지만 정확성을 보장한다”라는 표현은 약간 수정이 필요하다.

정확성은 알고리즘 자체의 증명 문제이므로:

• 잘 설계된 그리디는 정확하다.
• 잘못 설계된 DP는 틀릴 수 있다.

따라서 일반적으로는 다음처럼 정리하는 것이 가장 적절하다.

• 그리디: 빠르고 구현이 간단하지만 최적성 증명이 필요하다.

 

 

 

해당 문제는 배낭문제와 유사하다.

 

이 문제는 전형적인 0/1 배낭(Knapsack) 계열 DP와 가장 흡사하다.

특히 느낌은:

• 물건마다 선택지가 2개 있고
• 누적 비용(흔적)을 관리해야 하며
• 제한 조건을 넘지 않도록 하면서
• 어떤 값을 최소화/최대화

한다는 점에서 거의 배낭 구조다.

구체적으로 대응시키면:

• 물건 i
  → 배낭의 아이템
• A가 훔친다 / B가 훔친다
  → 아이템 선택 방식
• A 흔적, B 흔적
  → 무게(weight) 혹은 비용(cost)
• 경찰에 안 잡혀야 함
  → 용량 제한(capacity)
• A 흔적 최소화
  → 최적화 목표

특히 이 문제는 다음 형태와 매우 비슷하다.

“한쪽 비용 제한 안에서 다른 쪽 비용 최소화”

즉:

• B 흔적은 m 미만이어야 하고
• 그 조건을 만족하면서
• A 흔적 최소화

이 구조다.

 

 

 

 

 

 

그리디 VS  DP  개념 블로그 참고해보기

 

https://brynn-park.tistory.com/41

Greedy vs. DP(Dynamic Programming)

 

 

---

 

그리 vs DP 구분법 (실전용)

1. 그리디를 먼저 의심하는 경우

다음 중 하나라도 강하면 그리디 후보다:

• 현재 선택이 “전체 최적”에 영향을 거의 안 주는 느낌이다
• 정렬 후 규칙적으로 풀릴 것 같다
• “지금 가장 좋은 선택”이 자연스럽게 보인다
• 선택이 이후 상태를 크게 복잡하게 만들지 않는다
• 교환해도 결과가 유지될 것 같다 (교환 논법 가능 느낌)

👉 한마디:

“지금 최선 선택 = 전체 최선” 느낌이면 그리디

---

2. DP를 써야 하는 경우

다음 특징이면 DP다:

• 현재 선택이 미래 선택에 영향을 크게 준다
• “어떤 선택을 하느냐에 따라 상태가 완전히 달라진다”
• 경우의 수가 너무 많아서 완전탐색 불가능
• 같은 상태가 여러 경로로 반복된다
• “~까지의 최적값 / 경우의 수” 형태가 보인다

👉 한마디:

“선택에 따라 미래가 갈리고, 같은 상태가 반복된다” → DP

---

3. 가장 중요한 핵심 기준 (시험용 1줄)

그리디: “지금 선택이 곧 답이 된다”가 증명 가능
DP: “모든 선택을 고려해야 최적을 보장할 수 있다”

---

4. 빠른 판단 체크리스트

그리디 체크

• 정렬하면 풀릴 것 같다?
• 반례 찾기 어렵다?
• 선택 기준이 하나로 정해진다?

→ YES 많으면 그리디 의심

---

DP 체크

• 선택이 2개 이상이고 이후 영향이 크다
• 상태를 저장해야 할 것 같다
• “부분 문제 반복” 느낌이 있다

→ YES 많으면 DP

---

5. 핵심 요약

• 그리디 = “선택 1개로 끝나는 구조”
• DP = “선택을 다 저장해야 하는 구조”
• 둘 다 아니면 보통 그래프/탐색/비트마스크

 

 

해당 문제가 DP 쪽인지 체크

1. 선택이 누적된다 → DP 신호

각 물건마다 선택이 있음:

• A가 훔침 → A 흔적 증가
• B가 훔침 → B 흔적 증가

이 선택이 계속 누적돼서
현재 선택이 미래 가능 여부를 바꾼다

→ 전형적인 DP 조건

 

2. “지금 A/B 중 더 작은 것”이 항상 최적이 아님 → 그리디 실패 구조

예를 들어:

• 지금은 A로 하면 흔적이 적어 보임
• 하지만 나중에 A 제한(n)에 빨리 도달하면 전체가 터짐

즉:

지역 최적 선택 ≠ 전체 최적

→ 그리디 구조 붕괴

 

3. 상태가 2개 축이다

• A 누적 흔적
• B 누적 흔적

이건 사실상:

2차원 자원 관리 문제

→ 전형적인 DP (knapsack 변형)

 

4. “남은 선택이 미래 가능성을 결정”함

이게 핵심인데:

• 어떤 물건을 A로 선택하면
  → B 여유가 늘어남
• 반대로 B로 선택하면
  → A 여유가 늘어남

즉 선택이 독립이 아니라 서로 얽혀 있음

→ 그리디 성립 거의 불가능

그리디 체크는 거의 안 통함

그리디가 맞으려면 보통 이런 게 있어야 함:

• 정렬 기준 하나
• 선택 기준 하나
• 선택이 미래를 망치지 않음

근데 이 문제는:

• 기준이 2개 (A, B)
• 선택이 미래 제약을 바꿈
• trade-off 구조

→ 그리디 조건 거의 전부 깨짐

결론

이 문제는 그리디 체크보다 DP 체크가 훨씬 강한 전형적인 2차원 DP 문제다.

 

---

시간제한선택

 

이 문제는 info 길이 최대 40이니까:

 

 

2^40 = 약 1,099,511,627,776 = 약 1조

10^8 기준으로 1만 배 넘어서 완전히 시간초과다.

---

기준 정리:

크기	가능한 알고리즘
n ≤ 20	2^n 브루트포스 가능
n ≤ 40	브루트포스 불가, DP/분할정복
n ≤ 100	O(n^3) 이하
n ≤ 1000	O(n^2) 이하
n ≤ 100,000	O(n log n) 이하
n ≤ 1,000,000	O(n) 이하