[백준] 17234 : ScoringHack

https://www.acmicpc.net/problem/17234

문제 분석

 문제는 0점부터 시작하여 3가지 선택을 반복하며,
$($1. 점수에 a점 추가  2. 점수에 b점 추가 3. 점수를 2배$)$
두 가지 조건을 만족시키며
$($1. 점수가 N+a 미만 2. 2배 한 횟수가 전체의 10% 이하$)$
가장 빨리 N에 도달하는 문제이다.

 기본적으로 점수, 턴 수, 2배 횟수 총 3가지를 고려해야 하므로 시간복잡도 $N^3$의 DP 문제로 하면 복잡도가 1억이 초과하여 불가능해 보인다.$($안 해봐서 모른다 의외로 될지도 굉장히 애매한 복잡도$)$ 하지만, N이 500 이하이므로 2배를 수행하는 선택이 10번 이상 나오면 값이 최소 1024$(=2^{10})$이므로 10번 이상의 2번 연산은 배제하면 되어 $10*N^2 = 2.5E6$의 복잡도에서 계산가능하다.

문제 해결 전략

• 10번 이상 2배를 선택했는지는 어차피 조건1에서 걸리므로 굳이 체크 안 한다.
• 코드 간략화를 위해 비효율적이지만 3가지 선택에 대해서 조건 1과 조건 2를 동시에 체크하도록 구성했다.
• DP는 효율을 위해 배열이아닌 set을 기반으로 구성했다. 이래야지 $O(n^3)$이 안된다.

1. DP내에서 값하나를 뽑는다.
2. 뽑은 값에대하여 3가지 선택을 수행하여 다음 값을 생성한다.
3. 다음값에대해서 조건 1, 조건 2를 체크한다.
4. 조건에 위반되지 않으면 ndp에 해당값을 넣는다.
5.dp에 ndp를 move 시키고 ndp는 초기화한다.
6.1-5의 과정을 다음 값이 N을 넘을 때까지 반복한다. 

코드

#include <iostream>
#include <set>

using namespace std;

//문제분석
//문제는 3가지 선택을 반복하며      (+a, +b, X2) 
//두가지 조건을 만족시키며          (score<N+a, 10*N(X2)<x) 
//가장 빨리 N에 도달하는 문제이다.
//기본적으로 점수, 턴수, 2배 횟수를 고려해야해서 N^3의 복잡도의 DP 같아보이지만
//실제로 2배는 10번이상 할수없어(n이 500이라 10번하면 최소 1024라 조건 만족 안함)
//10*N^2=2.5E6의 복잡도에서 작동한다.
//=====================================================================
//해결전략
//점수와 2배 횟수를 같이 페어로 가지는 자료형 선언
//그자료형으로 set을 기반으로 dp 수행
//1.현재 dp에서 값을 하나 뽑아옴
//2.뽑아온 값에 3가지 선택을 수행하여 다음 값 생성 (이때, 2배는 조건 계속체큰)
//3.ndp에 해당값 넣음
//4.ndp가 dp가되고 ndp 초기화
//5.1-4를 N도달 전까지 반복시 탈출
//=====================================================================
//필요자료형
//변수
//pair<int,int> score_t : 실점수와 2배횟수 저장
//set<score_t> dp,ndp : dp하기 위한 set / ndp는 반복문 내에 로컬로 선언(자동 초기화)
//함수
//굳이 없음

typedef pair<int,int> score_t;
int N,a,b;

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> a >> b;
    set<score_t> dp=set<score_t>(),ndp=set<score_t>();
    dp.insert(make_pair(0,0));
    int result(0);
    for (int i = 1; (i < N+1)&&!result; i++,dp=move(ndp),ndp=set<score_t>())
    {   
        for(auto val : dp){
            score_t nxtVals[3] = {
                make_pair(val.first+a,val.second), 
                make_pair(val.first+b,val.second), 
                make_pair(2*val.first,val.second+1)
            };

            for(auto nxtVal : nxtVals){
                if(nxtVal.first>=N+a || i<10*nxtVal.second) continue;
                (nxtVal.first>=N) ? (result=i) : (ndp.insert(nxtVal),0);
            }
        }
    }
    
    cout << result;
}