백준 2839번

2839번: 설탕 배달

3과 5를 최대한 적게 이용하여 n을 만들 때 최대한 적은 경우의 수를 찾아내는 프로그램이다.

DP에 대한 개념이 부족한거 같아 추가적으로 DP문제를 조금 더 풀어보고자 풀어본 문제이다.

 

풀이

1~n까지 반복하면서 n-3, n-5중에 작은 값을 찾아서 +1을 해주면 된다. 

arr [3]은

초기 값으로 1로 세팅해 준다.

4는 3과 5를 이용하여 나올 수 없기 때문에 -1이 된다.

 

5는 5만 이용하면 되기 때문에 1이 된다.

 

6은 dp [6-3] 또는 dp [6-5]의 값들 중 작은 값을 찾아 +1을 하면 된다. 이때 예외처리가 필요한데

dp [6-5]는 현재 표에서는 없지만 배열에서는 0의 값이 들어가 있게 되다. 이때 그냥 작은 수로 비교해 버리면 0을 선택해 버려서 6에 1이 들어가기 때문에 문제가 생긴다. 그래서 조건을 추가해 비교하는 2개의 값들 중 -1,0이 없는지 확인해야 한다.

 

7의 경우 dp [7-5], dp [7-3]을 비교해야 하는데 2개의 값이 0과 -1이 된다. 0과 -1이라는 의미는 해당 숫자가 5와 3을 이용해 표현할 수 없다는 의미기 때문에 -1을 넣어줘야 한다.

 

8의 경우 dp [8-3], dp [8-5]의 값들 중 작은 것을 비교해 +1을 해주면 된다.

 

따라서 점화식은 다음과 같다.

dp [4], dp [7] = -1

dp [n-3] <= 0 || dp [n-5] <= 0의 경우 둘 중에 0이 아닌 값 dp [n]

dp [n] = Math.min(dp [n-3], dp [n-5])

 

코드

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int [] dp = new int[n+1];
        dp[3] = 1;
        for(int i = 4;i<=n;++i)
        {
            if(i==4||i==7)
            {
                dp[i] = -1;
                continue;
            }
            if(dp[i-3] <= 0 || dp[i-5]<=0)
            {
                if(dp[i-3]<=0)
                {
                    dp[i] = dp[i-5]+1;
                }else{
                    dp[i] = dp[i-3]+1;
                }
            }else{
                dp[i] = Math.min(dp[i-3],dp[i-5])+1;
            }

        }
        System.out.println(dp[n]);


    }

}