목표 점수 target이 매개변수로 주어졌을 때 최선의 경우 던질 다트 수와 그 때의 "싱글" 또는 "불"을 맞춘 횟수(합)를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한사항
1 ≤ target ≤ 100,000
문제해결
일단 문제는 1~20까지의 값이 싱글,더블,트리플. 그리고 불(50)이라는 값이있다.
원하는 값은 싱글,불을 맞춘횟수와 최선의 경우의 다트수이다.
그러면 일단 dp[60]까지는 직접 설정이 가능하지만 그 이후는 점화식이 필요하다.
그러면 dp[n]= Min(dp[i-50],dp[i-60])이므로 이것을 통해서 target까지 구하면 된다.
코드(테스트케이스 실패)
class Solution {
public int[] solution(int target) {
int[][] map = new int[100001][2];
map[0][0] =0;
map[0][1] =0;
init(map);
DP(target,map); //값이 60초과한 값(DP)
int[] answer = map[target];
return answer;
}
void DP(int target,int[][] map){
for(int i=61;i<=target;i++){
// 3가지 경우가 있다 DP[i-50][0] DP[i-60][0]의 값이 같은경우, i-50이 클때 작을때
if(map[i-50][0]==map[i-60][0]){
map[i][0] = map[i-50][0]+1;
map[i][1] = Math.max(map[i-50][1]+1,map[i-60][1]);
}else if(map[i-50][0] > map[i-60][0]){
map[i][0] = map[i-60][0]+1;
map[i][1] = map[i-60][1];
}else{
map[i][0] = map[i-50][0]+1;
map[i][1] = map[i-50][1]+1;
}
}
}
void init(int[][] map){
for(int i=1;i<=60;i++){
// 싱글 +불
if(i<=20||i==50){
map[i][0] = 1;
map[i][1] = 1;
}else if(i<=40&&i%2==0){ // 더블
map[i][0] = 1;
map[i][1] = 0;
}else if(i<=60&&i%3==0){ // 트리플
map[i][0] = 1;
map[i][1] = 0;
}else if(i<=40){ //더블이 아닌 40 이하의 값
map[i][0] = 2;
map[i][1] = 2;
}else if(i>50&&i<=60){// 싱글+불로 표현되는 60이하의 값.
map[i][0] = 2;
map[i][1] = 2;
}else{// 그 외의 값.
map[i][0] = 2;
map[i][1] = 1;
}
}
}
}//메모이제이션문제이렇게 풀면 결과는 맞지만 실제 테스트케이스 몇개를 해보면 해결이 안되는 문제가 있다.
결국 싱글,더블,트리플,불이 되는 모든 값을 찾아봐야한다.
코드 (해결완료)
class Solution {
public int[] solution(int target) {
int[][] map = new int[100001][2];
map[0][0] =0;
map[0][1] =0;
for (int t = 0; t <= target; t++)
map[t] = new int[] {10000000, -10000000};
init(map);
DP(target,map); //값이 60초과한 값(DP)
int count =0;
while(target>360){
count++;
target-=60;
}
int[] answer = map[target];
answer[0]+=count;
return answer;
}
void DP(int target,int[][] map){
for (int n = 61; n <= 360; n++) {
for(int i=1;i<=20;i++){
int s= n - i;
int d= n - (i*2);
int t= n - (i*3);
if(map[d][0] < map[n][0]){
map[n][0] = map[d][0] +1;
map[n][1] = map[d][1];
}
if(map[t][0] < map[n][0]){
map[n][0] = map[t][0] +1;
map[n][1] = map[t][1];
}
if(map[s][0] < map[n][0]){
map[n][0] = map[s][0] +1;
map[n][1] = map[s][1] +1;
}
}
int b = n-50;
if(map[b][0] < map[n][0]){
map[n][0] = map[b][0] + 1;
map[n][1] = map[b][1] + 1;
}
}
}
void init(int[][] map){
for(int i=1;i<=60;i++){
// 싱글 +불
if(i<=20||i==50){
map[i][0] = 1;
map[i][1] = 1;
}else if(i<=40&&i%2==0){ // 더블
map[i][0] = 1;
map[i][1] = 0;
}else if(i<=60&&i%3==0){ // 트리플
map[i][0] = 1;
map[i][1] = 0;
}else if(i<=40){ //더블이 아닌 40 이하의 값
map[i][0] = 2;
map[i][1] = 2;
}else if(i>50&&i<=60){// 싱글+불로 표현되는 60이하의 값.
map[i][0] = 2;
map[i][1] = 2;
}else{// 그 외의 값.
map[i][0] = 2;
map[i][1] = 1;
}
}
}
}//메모이제이션문제
not null