[백준/JAVA] 2839번: 설탕 배달

🔺 문제

2839번: 설탕 배달

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int cnt = 0;
        
        while(true) { 
            if(N % 5 == 0) {
                cnt += N / 5;
                System.out.println(cnt);
                break;
            }
            else {
                N -= 3;
                cnt++;
            }
            
            if(N < 0) {
                System.out.println(-1);
                break;
            }
        }
    }
}

✅ 해결 아이디어
- 무게가 5로 나눠진다면, 5kg을 이용해 들 수 있는만큼 갯수 더해 출력
- 무게가 5로 나눠지지 않는다면, 여기서 3kg을 빼고 갯수 + 1을 해 반복문을 다시 돌린다.

- 위의 조건식에 부합하지 않고, 무게가 0보다 작다면, 3kg나 5kg 봉지를 이용해 들 수 없으므로 -1 출력.

 

 

---

🔺 다른 풀이들

- 쉽게 푸셨다... wow

백준 2839번 설탕배달 자바(Java)

백준 2839번 java 자바 설탕배달 (수학 1)

---

💬 느낀 점

내가 첨에 생각했던 거는 약간 아래 풀이랑 비슷허다.

 

[백준] 2839번 : 설탕 배달 - JAVA [자바]

 

 

아무튼,,, 괜히 dp 식 세운다고 고민했는데 그럴 필요가 없었던 것이었다,,^^

DP 아니고 그리디 문제 같이 더 느껴져서 암튼,,, 끝..

1회독	2회독	3회독	4회독	5회독
V	230705	240116	240630

 

 

(+ 2회독 240116)

DP 점화식을 사용해 풀어보았다

 

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MAX = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
 
        int[] dp = new int[5001];
        Arrays.fill(dp, MAX);        
        dp[3] = 1;
        dp[5] = 1;
        
        if(N <= 5) {
            System.out.println(dp[N] == MAX ? -1 : dp[N]);
            return;
        }
        
        for(int i = 6 ; i <= N ; i++) {            
            for(int j = 3 ; j <= N - 3 ; j++) {
                if(dp[j] != MAX && dp[i - j] != MAX) {
                    dp[i] = Math.min(dp[i], dp[i - j] + dp[j]);
                }
            }            
        }
        
        System.out.println(dp[N] == MAX ? -1 : dp[N]);
    }
}
 

 

 

 

(+3회독 240630 14296KB, 152ms)

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int MAX = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        int[] dp = new int[5001];
        Arrays.fill(dp, MAX);
        
        dp[3] = 1;
        dp[5] = 1;
        
        for(int i = 3 ; i <= N ; i++) {
            for(int x = 1 ; x <= i/2 ; x++) {
                if(dp[x] != MAX && dp[i-x] != MAX)
                    dp[i] = Math.min(dp[i], dp[x] + dp[i-x]);
            }
        }
        
        System.out.println(dp[N] == MAX ? -1 : dp[N]);
    }
}

---

(참고)

✔ 쉬운 풀이 짱,,,

백준 2839번 설탕배달 자바(Java)