글 읽기 - 코린이 도와주세요 ㅠ

damin8 4년 전 0

오랜시간 고민해서 풀어봤는데요... 어떠한 반례가 있을까요? 도움 부탁드립니다 ㅠ

#include<iostream>
#include<algorithm>
using namespace std;

int dp1[10001], dp2[10001];

int main() {
	ios_base::sync_with_stdio;
	cin.tie(NULL); cout.tie(NULL);
	int n, k, x;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> x;
		for (int z = 1; z <= k; z++) {
			if (i == 0) {
				if (z%x == 0) dp1[z] = z / x;
				else dp1[z] = 1e9;
			}
			else {
				if (z - x < 0) dp2[z] = dp1[z];
				else {
					if (z%x != 0) {
						dp2[z] = min(dp1[z], dp2[z - x] + dp2[x]);
						dp1[z] = dp2[z];
					}
					else {
						dp2[z] = min(dp1[z], z / x);
						dp1[z] = dp2[z];
					}
				}
			}
		}
	}
	if (dp2[k] != 1e9) cout << dp2[k] << "\n";
	else cout << "-1\n";
}

seico75 4년 전 1

1 25
5

damin8 4년 전 0

감사합니다!!! 덕분에 풀었습니다!!

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

문제

문제

출처

ICPC

코린이 도와주세요 ㅠ

damin8 4년 전 0

seico75 4년 전 1

damin8 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말