[Java 자바] 백준 알고리즘 2839번 답 : 설탕 배달

[Java 자바] 백준 알고리즘 2839번 답 : 설탕 배달

728x90

반응형

SMALL

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

이 문제,, 다이나믹 프로그래밍으로 분류되어있길래 나는 다이나믹 프로그래밍을 할 줄 몰라서,, 익히고나서 푼 문제!

https://youtu.be/5Lu34WIx2Us

[나동빈님 이코테 강의 (3회 반복) + 이코테 책] 공부해서 이해했음..ㅠ

이거 은근 코드는 엄청 짧은데 생각하는게 어려웠다.

그래서 이코테 교재로 공부하다보니 이해가 되더라!

내가 이해한 부분은 추후 유튜브에 업로드할 예정!.!

암튼 그래서 DP 알고리즘을 적용해서 풀었는데 더 효율적으로 푼 방식이 있더라..!

그리디 기법을 쓰면 DP를 이용하지 않고도 풀 수 있는데,, 음,, 근데,, 한번에 떠올리기는 어려운 알고리즘이다.

코드는 매우매우 간단하고 쉽지만, 나라면 이 로직을 절대 생각 못했을 것 같다..ㅎ

[DP 알고리즘 적용]

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 [] d = new int[N+1]; d[1] = -1; d[2] = -1; d[3] = 1; if(N>=4) d[4] = -1; for(int i=5;i<=N;i++){ if(i%3==0 || d[i-3] > 0) d[i] = d[i-3]+1; if(i%5==0 || d[i-5] > 0) { if(d[i] != 0) d[i] = Math.min(d[i],d[i-5]+1); else d[i] = d[i-5]+1; } if(d[i] == 0) d[i] = -1; } System.out.println(d[N]); } }

[더 쉬운 알고리즘]

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 ans = 0; while(N>0){ if(N % 5 == 0){ ans++; N-=5; } else{ ans++; N-=3; } } if(N < 0) System.out.println(-1); else System.out.println(ans); } }

728x90

반응형

LIST

from http://zzinise.tistory.com/79 by ccl(A) rewrite - 2021-09-09 21:01:19