프로그래머스 문제 - 카운트 다운

프로그래머스 카운트 다운 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

1부터 20까지 수가 있고 각 수에 "싱글","더블","트리플"칸이 있습니다. 싱글은 해당 수만큼 점수를 얻으며 더블은 해당 수의 2배, 트리플은 해당 수의 3배만큼 점수를 얻습니다.
가운데는 "불"이며 50점의 점수를 얻습니다.
두 선수가 번갈아가며 한번 씩 다트를 던지며 0점을 만든 사람이 승리하며 같은 수의 다트를 던졌을 경우 "싱글"과 "불"을 더 많이 맞춘 선수가 이기며마저 같으면 선공을 한 선수가 승리합니다.
목표 점수 target이 정해졌을 때 최선의 경우로 다트를 던질 횟수와 "싱글"과"불을 맞춘 횟수를 배열에 담아 리턴해야 합니다.

문제 풀이

최선의 경우는 다트를 최소한으로 던졌을 때와 그 중 "싱글"과"불"을 최대한으로 맞춘 상황을 찾아야합니다.

기본적으로 문제가 다트판이기에 목표점수가 일정 이하일 경우에는 손쉽게 답을 찾아낼 수 있습니다.
target이 20보다 작거나 50일 경우 한 개의 다트만으로 목표치를 달성함과 동시에 "싱글"과"불"을 맞추게 되므로 [1,1]이 됩니다.
target이 40보다 작고 2의 배수일 경우 한 개의 다트만으로 목표치를 달성함으로 [1,0]이 됩니다.
target이 60보다 작고 3의 배수일 경우 한 개의 다트만으로 목표치를 달성함으로 [1,0]이 됩니다.
target이 50보다 크거나 70보다 작거나 같을 경우 두 개의 다트만으로 목표치를 달성함과 동시에 둘 다 "싱글"과"불"을 맞추게 되므로 [2,2]가 됩니다.
위의 반례에 속하지 않으며 target이 70보다 작을 경우 두가지의 경우가 추가적으로 생깁니다.
target이 40보다 작은 경우 두 개의 다트만으로 목표치를 달성함과 동시에 둘 다 "싱글"과"불"을 맞추게 되므로 [2,2]가 됩니다.
이후의 나머지 수들은 두 개의 다트만으로 목표치를 달성함과 동시에 한 가지의 "싱글"과"불"을 맞추게 되므로 [2,1]가 됩니다.

위의 모든 반례에 속하지 않는 경우는 이후의 최선의 답을 생각하기 위해 제일 큰 수인 60과 "불"에 해당하는 50을 가지고 계산해야 합니다.
대부분의 경우는 50을 빼서 "싱글"과"불"을 맞춘 횟수를 최대한으로 하며 던진 다트의 수를 최소한으로 하면 되지만, 숫자가 일정 이상 커지거나 다른 경우로 60을 빼서 던진 다트의 수가 50을 뺀 경우보다 더 적은 상황이 있습니다.

그러니 전에 계산했던 값들 중 60을 뺀 결과와 50을 뺀 결과값들을 기반으로 다트의 던진 수를 비교한 후 더 최적에 가까운 값을 찾아 저장해주면 됩니다.

전체 코드

dp문제를 풀며 천천히 풀어나가는 법을 더 해봐야 할 것 같습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(int target) {
    vector<int> answer;
    int dp[100001][2] = {0,};
    
    for(int i = 1; i <= target; i++)
    {
        if(i <= 20 || i == 50)
        {
            dp[i][0] = 1;
            dp[i][1] = 1;
        }else if(i <= 40 && i % 2 == 0)
        {
            dp[i][0] = 1;
            dp[i][1] = 0;
        }else if(i <= 60 && i % 3 == 0)
        {
            dp[i][0] = 1;
            dp[i][1] = 0;
        }else if(i >= 51 && i <= 70)
        {
            dp[i][0] = 2;
            dp[i][1] = 2;
        }else if(i < 70)
        {
            if(i < 40)
            {
                dp[i][0] = 2;
                dp[i][1] = 2;
            }else
            {
                dp[i][0] = 2;
                dp[i][1] = 1;
            }
        }else{
            //60을 쓰는 경우와 50을 쓰는 경우의 다트를 던진 수가 같을 경우
            if(dp[i-60][0] == dp[i-50][0])
            {
                dp[i][0] = dp[i-50][0]+1;
                dp[i][1] = max(dp[i-60][1], dp[i-50][1]+1);
            }else if(dp[i-60][0] < dp[i-50][0]) //60을 쓰는 경우가 50을 쓰는 경우보다 다트를 던진 수가 적을 경우
            {
                dp[i][0] = dp[i-60][0]+1;
                dp[i][1] = dp[i-60][1];
            }else   //60을 쓰는 경우가 50을 쓰는 경우보다 다트를 던진 수가 적을 경우
            {
                dp[i][0] = dp[i-50][0]+1;
                dp[i][1] = dp[i-50][1]+1;
            }
        }
    }
    
    answer.push_back(dp[target][0]);
    answer.push_back(dp[target][1]);
    
    return answer;
}

출처

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