-
[C++] 프로그래머스 카운트 다운알고리즘/프로그래머스 2024. 4. 1. 17:49반응형
전형적인 DP 문제
다트를 던져서 가질 수 있는 점수를 초기화하고 1~100,000 까지의 점수들에 대해 반복문을 돌리면 된다.
#include <string> #include <vector> #include <set> #define INF 1e9 using namespace std; long long dp[100002]; int dp_sum[100002]; set<int> se; bool check[61]; void init() { for(int i=0; i<=100000; i++) { dp[i] = INF; } for(int i=1; i<=20; i++) { for(int j=1; j<=3; j++) { se.insert(i * j); dp[i * j] = 1; if(j == 1) { check[i * j] = true; dp_sum[i * j] = 1; } } } check[50] = true; dp[50] = 1; dp_sum[50] = 1; se.insert(50); } vector<int> solution(int target) { vector<int> answer; init(); int dart = 0, sum = 0; for(int i=1; i<=100000; i++) { for(int s : se) { int tmp = i - s; if(tmp <= 0) { continue; } if(dp[i] == dp[tmp] + 1 && dp_sum[i] <= dp_sum[tmp]) { if(check[s]) { dp_sum[i] = dp_sum[tmp] + 1; continue; } dp_sum[i] = dp_sum[tmp]; } else if(dp[i] > dp[tmp] + 1) { dp[i] = dp[tmp] + 1; if(check[s]) { dp_sum[i] = dp_sum[tmp] + 1; continue; } dp_sum[i] = dp_sum[tmp]; } } } answer.push_back(dp[target]); answer.push_back(dp_sum[target]); return answer; }
728x90반응형'알고리즘 > 프로그래머스' 카테고리의 다른 글
[C++] 프로그래머스 거스름돈 (0) 2024.04.01 [C++] 요격 시스템 (3) 2023.04.17 [C++] 프로그래머스 연속된 부분 수열의 합 (0) 2023.04.13 [C++] 프로그래머스 광물 캐기 (0) 2023.03.23 [C++] 프로그래머스 리코쳇 로봇 (0) 2023.03.22