[백준:2839] 설탕 배달 (JAVA)

2023년 첫 게시물이자,, 첫 알고리즘 문제를 풀어보았다.
퇴사준비와 연말행사가 겹치는 바람에 거의 1~2주를 공부에 집중하지 못하고 보냈다,,😢
이제 퇴사도 했겠다. 정신차리고 다시 달려보자!! 라는 다짐을 하며 오늘 풀어 본 문제를 포스팅 해보도록 하겠다.

DP 유형의 문제를 풀어보려고 제일 쉬운 난이도의 문제를 골랐는데,,
그냥 수학적인 접근 방법으로 풀어버렸다,,ㅎ,,,,

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    System.out.println(dp(N));
}

public static int dp(int N){
    int answer = 0;
    while(true) {
        if (N % 5 == 0) {
            answer += N / 5;
            break;
        } else if (N < 0) {
            answer = -1;
            break;
        }
        N -= 3;
        answer++;
    }
    return answer;
}

아무래도 아직 DP로 접근하는 방법이 익숙하지 않아서라고 생각하고,
DP풀이를 검색해가며 다시 풀어보았다.

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    System.out.println(dp(N));
}

public static int dp(int N){
    int[] dp = new int[N+1];

    if(N>=3){
        dp[3] = 1;
    }
    if(N>=5){
        dp[5] = 1;
    }

    for(int i=6; i<=N; 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-3], dp[i-5]) +1;
            }
        }
    }

    if(dp[N] == 0){
        dp[N] = -1;
    }
    return dp[N];
}

아직 익숙한 풀이 방법이 아니라서 솔직히 100퍼센트 이해하지는 못했다.
하지만 반복이 답이다!
계속 비슷한 유형의 문제를 풀다보면 익숙해져서 이해도 완벽히 하게되는 날이 올 것이라 확신한다!😤

---

그런데 이 문제는 어렵지 않은 문제라서 그런지,,
수학적으로 접근해서 풀어도 복잡도가 높지 않아서 그런지 두 풀이의 차이가 거의 없었다.

위에가 DP로 푼 결과이고, 아래가 수학적으로 푼 결과이다.

DP 알고리즘의 다른 문제들도 수학적으로 풀 수 있을 것 같으면 두가지 경우 모두 풀어보고 비교해봐야겠다.