- 그냥 메모리를 사용해서 버틸 수 있는 무게 별로 최대가치를 저장하는 테이블을 선언하자 라고 생각.
- N개의 물건들을 하나씩 살펴 보면서 버틸 수 있는 무게 K 밑으로 살펴보며 이 물건을 넣어가며 테이블을 갱신
2. 주의사항
- 아직 알고리즘 문제풀이가 많이 부족해서 기존의 떠오른 생각 방향에서 다른 쪽으로 생각하는게 부족...
- 열심히 풀어야겠습니다...
3. 나의코드
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int N, K;
int dp[100001]; // 버틸 수 있는 무게 별로 최대가치를 저장하는 테이블
int weightarr[101];
int valuearr[101];
void dypro() {
for (int i = 1; i <= N; i++) {
for (int j =K; j >= 0; j--) {
if (weightarr[i]<= j) {
dp[j] = max(dp[j], dp[j- weightarr[i]] + valuearr[i]);
}
}
}
cout << dp[K] << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> weightarr[i] >> valuearr[i];
}
dypro();
return 0;
}
- (A+B) % MOD = (A%MOD +B%MOD) % MOD (이 문제에서는 필요없지만 뺄셈도 같다.)
- (A*B) % MOD =(A%MOD * B%MOD) % MOD
-(50점)
3. 나의 코드
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int L;
cin >> L;
string s;
cin >> s;
long long mul = 1;
long long result = 0;
for (int i = 0; i < L; i++) {
result =(result+((s[i]-'a'+1)*mul))%1234567891;
mul = (mul * 31) % 1234567891;
}
cout << result<< "\n";
return 0;
}