풀이
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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이