글 읽기 - 질문있습니다. (16194번)

zkfzpf56 3년 전 0

dp[i][j]의 의미는, a[1]~a[i]까지 사용해서 j개를 구매할 때 지불하는 금액 입니다.

제가 어딘가 빠뜨린 부분이 있을까요 ?

#include <stdio.h>
int a[1001] = { 0, };
int dp[1001][10001] = { 0, };

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		dp[1][i] = a[1] * i;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			if ((j / i) * a[i] + dp[j % i][j % i] < dp[i - 1][j]) {
				dp[i][j] = (j / i) * a[i] + dp[j % i][j % i];
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	printf("%d", dp[n][n]);
}

wndyd9557 2년 전 0

반례

100 1 5 1 100 100 100 100 100

출력 : 15

정답 : 7

dp[i][j]가 최솟값을 가지지 않는 구간이 있습니다.

dp[4][9] 는

카드9 = 카드2 + 카드3 + 카드4 일 경우에 1 + 5 + 1이여서 7이 나와야 됩니당..!

간결하지 않은 dp를 만들어서 실수 하신듯 합니다..!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

질문있습니다. (16194번)

zkfzpf56 3년 전 0

wndyd9557 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말