[Java] 백준 2839번 : 설탕 배달 <Silver 4>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

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

2839번: 설탕 배달

Code

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(bf.readLine());
        ArrayList<Integer> dp = new ArrayList<>(Arrays.asList(10000,10000,10000,1,10000,1));
        int count = 6;
        
        while(count <= num){
            dp.add(Math.min(dp.get(count-3) +1, dp.get(count-5)+1));
            count++;
        }
        
        if(dp.get(num) > 9999){
            System.out.println(-1);
        }else{
            System.out.println(dp.get(num));
        }
    }
}

---

Code 필수 요소

1. DP 활용

2. 규칙 및 예외 확인법

 

이것만 생각해내면 절반은 끝났다.

 

// DP 활용

DP로 풀기위해서 점화식을 구하고자 했다.

1 : -1

2 : -1

3 : 1

4 : -1

5  : 1

6 : 2

7 : -1

8 : 2

9 : 3

10 : 2

 

이러한 순서로 값이 진행된다는 것을 파악할 수 있다.

5를 초과하는 숫자일 경우 해당 숫자에 3을 뺸 값과 5를 뺀 값 둘다 -1이 아닐경우 비교하여 둘중 더 작은 값 + 1의 값을 가진다. 

ex)

6

=> 3 : 1

     5 : -1

=> 6 : 2

 

// 규칙 및 예외 확인법

위의 규칙을 활용하여 해당 값은 -3을 한 값과 -5를 한 값중 더 작은 값으로 List를 채우는 방식으로 진행했다. 

이러한 방법의 문제점은 -1의 값이 나올때다. 그래서 -1인 값은 10000으로 초기화 하여 값을 무지하게 높여서 -1인 값과 정상적인 값을 비교하였을때 정상적인 값이 들어갈 수 있도록 했다. 

 

// 전체적 설명

값을 입력받고 해당 값들을 이용해서 바텀업 방식으로 정답을 찾아간다.

 

정답이 나오는 코드 자체를 짜는건 어렵지 않았다. 근데 문제는 DP를 활용하고 싶었어서 갈아엎고 다시 짰다. 물론 최적의 코드는 수학적으로 푸는거긴 하겠지만 지금은 알고리즘 공부니까...

-꿑-