코드 복사/붙여넣기 하는 당신이 아름답습니다.

2839 : 설탕배달

풀이

dp[i] = min(dp[i-3], dp[i-5]) + 1로 두고 풀면 된다.

n이 5천개니까 max를 대충 1600?쯤 잡으면 3으로 꽉채워도 최대 해보다 작고

max를 5천개 더해도 int 안쪽이니까 max를 2222로 잡았다.

코드

#include <stdio.h>
int min(int a, int b) { return a < b ? a : b; }
int main() {
	int n, i, a[5001];
	scanf("%d", &n);
	for (i = 0; i <= n; i++) a[i] = 2222;
	a[3] = a[5] = 1;
	for (i = 6; i <= n; i++) a[i] = min(a[i - 3], a[i - 5]) + 1;
	if (a[n] >= 2222) printf("-1");
	else printf("%d", a[n]);
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-14 09:54

Read more posts by this author