[프로그래머스/C++] 카운트 다운

 

 

문제

문제 설명

 

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 다트를 던져서 최소한의 횟수로 일정 점수를 획득하고, 최소한의 횟수 중에서도 싱글과 불을 가장 많이 던지도록 하는 문제다.

 

이 문제는 DP로 쉽게 풀 수 있다.

A라는 점수를 얻기 위한 최소한의 횟수를 구하려면, 아래와 같이 표현 할 수 있다.

[B + 다트 점수] = A 

여기서 B는 B라는 점수를 얻기 위한 최소한의 횟수다.

그리고 다트 점수는 내가 한번 던져서 나올 수 있는 점수들을 의미한다.

그러므로 A점수를 얻기 위한 최소 횟수를 구하기 위해서는, 이전의 B점수에 대한 최소 횟수를 알면 되므로 DP로 풀 수 있는 것이다.

 

처음에는 [A-다트점수]=B를 이용해 A를 구하려고 했지만, 이보다 더 직관적으로 풀 방법이 생각났다.

역으로 [현재 점수의 최소 횟수+다트 점수]를 계속 갱신하면 더 편하게 풀 수 있다.

 즉, 현재 점수에서 다트를 던지고 나온 점수를 비교하는 것이다.

 

예를 들어 내가 현재 1점이고 2점을 획득 할 경우 3점이 되는데, 기존에 저장된 3점을 획득하는 최적의 방법은 3점을 던져 1번에 획득하는 방법이다. 비교를 하면 1번 던져서 3점을 획득하는 방법이 더 횟수가 적으므로 갱신하지 않는다.

 

또 현재 2점이라면 1점을 던져 3점을 만들 수 있는데 마찬가지로 3점을 획득하는 최적의 방법이 1번 던지는 방법이기 때문에 갱신하지 않는다. 

이후 현재 점수가 3점이 되면 3점을 얻는 최적의 방법이 현재 3점에 저장되어 있게 된다.

 

​

[아이디어 정리]

1. 다트를 한번 던져서 나오는 경우를 전부 기록한다.
2. 이후 1점부터 target점수까지 for문을 돌리고, 그때마다 다트를 던져 점수를 획득하는 최소 횟수 기록을 갱신한다.
3. target점수에 저장된 최소 횟수와 그때의 싱글, 불 횟수를 return한다.

 

 

Code

 

 

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

vector<int> solution(int target) {
    vector<int> answer(2);
    vector<pair<int,int>> record(target+61,make_pair(100001,0));
    for (int i=1; i<=20; i++)
    {
        record[i].first=1;
        record[i].second=1;
        record[i*2].first=1;
        record[i*3].first=1;            
    }
    record[50].first=1;
    record[50].second=1;
    int sc2,sc3;
    for (int i=1; i<=target; i++)
    {
        for (int sc=1; sc<=20; sc++) //다트를 던지는 경우들
        {
            sc2=sc*2,sc3=sc*3;
            if (record[i+sc].first>record[i].first+1)
            {
                record[i+sc]=record[i];
                record[i+sc].first+=1,record[i+sc].second+=1;
            }else if(record[i+sc].first==record[i].first+1)
            {
                record[i+sc].second=max(record[i+sc].second,record[i].second+1);
            }
            
            if (record[i+sc2].first>record[i].first+1)
            {
                record[i+sc2]=record[i];
                record[i+sc2].first+=1;
            }else if(record[i+sc2].first==record[i].first+1)
            {
                record[i+sc2].second=max(record[i+sc2].second,record[i].second);
            }
            
            if (record[i+sc3].first>record[i].first+1)
            {
                record[i+sc3]=record[i];
                record[i+sc3].first+=1;
            }else if(record[i+sc3].first==record[i].first+1)
            {
                record[i+sc3].second=max(record[i+sc3].second,record[i].second);
            }
            //50점은 따로
            if (record[i+50].first>record[i].first+1)
            {
                record[i+50]=record[i];
                record[i+50].first+=1,record[i+50].second+=1;
            }
            else if(record[i+50].first==record[i].first+1)
            {
                record[i+50].second=max(record[i+50].second,record[i].second+1);
            }
        }
    }
    answer[0]=record[target].first;
    answer[1]=record[target].second;
    return answer;
}

 

---

 

처음에 역으로 계산하려다가 순차적으로 계산해도 똑같아서 더 빠르게 풀 수 있었다.

문제를 풀기는 쉬웠는데 방법 설명하는게 더 어려웠던 것 같다;;

 

프로그래머스