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

문제

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

프로그래머스

문제풀이

백준에서 DP로 풀었던 '1로 만들기'와 유사한 문제이다.

먼저 점수는 1~20, 1~20의 2의 배수, 1~20의 3의 배수, 50점 이렇게 있다.

셈을 하기 귀찮으므로 코드를 돌려 겹치는 부분을 제거했다.

여기서 중요한 점은 횟수는 최소로 하되, 횟수가 같으면 싱글(1~20), 불(50)을 최대한 많이 맞혀야 한다.

 

이중탐색을 통해 1점부터 시작하여 모든 과녁을 맞히는 경우를 탐색한다.

여기에 몇 가지 조건이 필요하다.

 

필수 조건은 과녁을 맞혔을 때 점수가 목표 점수이하여야 하다.

선택 조건은

1. 과녁을 맞혔을 때 점수가 처음 도달.

2. 점수를 이미 도달했다면 방금 던진 횟수를 포함하여 던진 다트 횟수가 적을 때

3. 점수도 같고 던진 횟수도 같지만, 싱글 or 불을 더 많이 맞혔을 때

이 세조건 중 하나라도 만족하면 다음으로 넘어간다.

 

현재 점수에 대한 정보를 갱신한다.

방금 던진 다트가 싱글이거나 불일 경우 횟수를 추가해 준다.

 

반복문이 종료될 때까지 위 작업을 반복하면 된다.

 

 

코드

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

vector<int> solution(int target) {
    int idx(0), idx2(0), next(0);
    vector<vector<int>>DP(target + 1, vector<int>(2, 0));
    vector<int>scores = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,26,27,28,30,32,33,34,36,38,39,40,42,45,48,50,51,54,57,60 };

    for (idx = 0; idx <= target; ++idx) {
        for (idx2 = 0; idx2 < scores.size(); ++idx2) {
            next = idx + scores[idx2];
            if (next <= target && (DP[next][0] == 0 || DP[idx][0] + 1 < DP[next][0] || (DP[next][0] == DP[idx][0] + 1 && DP[next][1] <= DP[idx][1]))) {
                DP[next][0] = DP[idx][0] + 1;
                DP[next][1] = DP[idx][1];

                if ((1 <= scores[idx2] && scores[idx2] <= 20) || scores[idx2] == 50) {
                    DP[next][1]++;
                }
            }
        }
    }
    return DP[target];
}