선밥의 공부하는 블로그

카운트 다운

문제 링크

카운트 다운

분석

target은 목표 점수를 의미합니다.
해당 목표 점수를 만들 때 다트 개수를 최소로 하고, 싱글 또는 불 개수가 가장 많은 값을 반환해야 합니다.
만약 다트 개수의 최소 수가 같고, 싱글 또는 볼 개수가 가장 많은 선수가 2명 이상인 경우 선공인 선수의 값을 반환해야 합니다.

싱글은 맞춘 수 만큼의 점수를 얻습니다.
더블은 맞춘 수의 두 배 점수를 얻습니다.
트리플은 맞춘 수의 세 배 점수를 얻습니다.
불과 아우터 불은 50점을 얻습니다.

다트 과녁은 1~20점 까지 있으므로, 싱글의 경우 최대 20점(불 50점), 더블의 경우 최대 40점, 트리플의 경우 최대 60점입니다.
점수의 가짓수는 총 61가지입니다.

풀이

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

// 주어진 값이 싱글 점수인지 여부를 판별
bool isSingle(int score)
{
    if (score == 50 || 1 <= score && score <= 20)
    {
        return true;
    }
    
    return false;
}

vector<int> solution(int target) {
    vector<int> answer;
    
    // 가능한 모든 다트 점수를 생성하여 저장
    vector<int> scores;
    for (int i = 1; i <= 20; ++i)
    {
        scores.push_back(i);
        scores.push_back(i * 2);
        scores.push_back(i * 3);
    }
    
    scores.push_back(50);
    
    // dp[i]에 최소 다트 수와 싱글 점수 수를 저장
    // 초기에는 모든 값이 불가능한 상태로 설정해준다.
    vector<pair<int, int>> dp(target + 1, {INT_MAX, 0});

    // 점수 0부터 갱신
    dp[0] = {0, 0};
    
    for (int i = 0; i <= target; ++i)
    {
        // 불가능한 상태는 건너뛴다.
        if (dp[i].first == INT_MAX)
        {
            continue;
        }
        
        // 가능한 모든 다트 점수를 사용
        for (int s : scores)
        {
            // i + s 점이 목표 점수를 넘는 경우 스킵
            if (i + s > target)
            {
                continue;
            }
            
            // 새로운 점수 i + s에 대한 다트 수
            int nextDartCount = dp[i].first + 1;
            int nextSingleCount = dp[i].second + (isSingle(s) ? 1 : 0);
            
            // 더 적은 다트 수로 만들 수 있는 경우 갱신
            if (dp[i + s].first > nextDartCount)
            {
                dp[i + s] = {nextDartCount, nextSingleCount};
            }
            // 같은 다트 수이면서 싱글 점수가 더 많은 경우 갱신
            else if (dp[i + s].first == nextDartCount && dp[i + s].second < nextSingleCount)
            {
                dp[i + s].second = nextSingleCount;
            }
        }
    }
    
    // 최종 정답 저장
    answer.push_back(dp[target].first);
    answer.push_back(dp[target].second);
    
    return answer;
}

성능 요약

시간 복잡도는 $O(target)$입니다.

  • 가능한 모든 다트 점수를 생성하여 저장하는 반복문 $O(61) \approx O(1)$
  • dp를 갱신하는 반복문 $O(target \times 61) \approx O(target)$
  • $O(1) + O(target)$

공간 복잡도는 $O(target)$입니다.

  • 가능한 모든 다트 점수를 생성하여 저장하는 벡터 vector<int> scores $O(61) \approx O(1)$
  • dp를 저장하는 벡터 vector<pair<int, int>> dp $O(target)$
  • $O(1) + O(target)$
테스트 성능

테스트 1 〉 통과 (0.01ms, 4.19MB)
테스트 2 〉 통과 (14.76ms, 4.2MB)
테스트 3 〉 통과 (10.04ms, 4.13MB)
테스트 4 〉 통과 (10.83ms, 4.2MB)
테스트 5 〉 통과 (11.81ms, 3.66MB)
테스트 6 〉 통과 (16.91ms, 4.16MB)
테스트 7 〉 통과 (11.16ms, 3.73MB)
테스트 8 〉 통과 (0.80ms, 4.14MB)
테스트 9 〉 통과 (12.88ms, 3.67MB)
테스트 10 〉 통과 (1.96ms, 3.66MB)
테스트 11 〉 통과 (2.44ms, 4.2MB)
테스트 12 〉 통과 (12.82ms, 4.16MB)
테스트 13 〉 통과 (3.74ms, 4.2MB)
테스트 14 〉 통과 (13.83ms, 4.18MB)
테스트 15 〉 통과 (11.44ms, 4.13MB)
테스트 16 〉 통과 (2.25ms, 4.16MB)
테스트 17 〉 통과 (1.54ms, 4.19MB)
테스트 18 〉 통과 (13.04ms, 4.16MB)
테스트 19 〉 통과 (6.04ms, 4.2MB)
테스트 20 〉 통과 (15.57ms, 4.13MB)
테스트 21 〉 통과 (0.02ms, 4.2MB)
테스트 22 〉 통과 (0.02ms, 3.66MB)
테스트 23 〉 통과 (0.02ms, 4.2MB)
테스트 24 〉 통과 (0.02ms, 4.14MB)
테스트 25 〉 통과 (0.02ms, 4.19MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글