[백준] 2839 설탕 배달

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

수학 카테고리에 있었는데 dp가 바로 떠올라서 이 방법으로 해결했다. 반복문을 계속 돌려서 풀 수도 있을 것 같다.

---

 

문제 및 입출력

---

 

코드

import java.util.Scanner;

public class Main
{
     public static void main(String[] args)
     {
         Scanner sc = new Scanner(System.in);
         int sugar = sc.nextInt();

         // 5 이하일 때는 예외처리
         if(sugar<5)
         {
             if(sugar==3 || sugar==5)
             {
                 System.out.println(1);
                 return;
             }
             else
             {
                 System.out.println(-1);
                 return;
             }
         }

         // dp용 배열 초기설정
         int[] dp = new int[sugar+1];
         dp[3] = 1;
         dp[5] = 1;

         // dp실행
         for(int i=6; i<=sugar; i++)
         {
             if(i%5==0)
              {
                  dp[i] = dp[i-5] + 1;
              }
             else if(i%3==0)
              {
                  dp[i] = dp[i-3] + 1;
              }
              else
              {
                  // 최소값으로 설정
                  if(dp[i-3]!=0 && dp[i-5]!=0)
                  {
                      dp[i] = Math.min(dp[i-5], dp[i-3]) + 1;
                  }
              }
          }

         // dp실행 후 0이면 조건불만족이므로 0 출력, 0이 아니면 dp[sugar] 출력
         System.out.println(dp[sugar]==0?-1:dp[sugar]);
     }
}