예산 : Summer/Winter Coding(~2018) ( 프로그래머스 / java )

programmers.co.kr/learn/courses/30/lessons/12982?language=java

코딩테스트 연습 - 예산

 

*해결과정

 dp로 푸는 방법과 일반적으로 접근하는 방법 2가지가 있다. 여기서 동전은 중복되서 사용되지 못하기 때문에 dp보다는 if문을 통해 바로 이동시켜 주는 것이 편리하다. dp로 계산하면 오히려 불필요한 연산들을 계속하여 O(동전의 갯수*예산)의 시간복잡도를 나타내고 통과는 하지만 효율적인 결과는 내지 못한다.

 

1. DP

import java.util.*;
class Solution {  
    int answer = 0;
    public int solution(int[] d, int budget) {
        Arrays.sort(d);
        int[] dp = new int[budget+1];
        for(int i=0;i<d.length;i++){
            for(int j=d[i];j<dp.length;j++){
                int first = dp[j];
                int second = dp[j-d[i]]+1;
                if(second>first){
                    dp[j] = second;
                    for(int k=j;k<dp.length;k++){
                        dp[k] = second;
                    }
                    break;
                } else dp[j] = first;
            }
        }
        return dp[budget];
    }
}

 

2. if문 처리

 

import java.util.*;
class Solution {
  public int solution(int[] d, int budget) {
      int answer = 0;
      int sum =0;
	   
	  Arrays.sort(d);	   
	   
	  for(int val : d) {
      	if(sum+val>budget){
        break;
        }
        
        else if(sum+val==budget){
        	answer++;
            break;
        }
        
        else {
        	sum+=val;
            answer++;
        }
      }
      return answer;
  }
}