[일반] c어케품?

[익명(219.254)]

배낭문제 비스무리한 dp문제 같아서 그리 접근햇는데 못풀었다 ㅠㅠ

[익명(118.41)]

팰린드롬인 숫자 n개를 뽑아놓고 n*n 배열 만든다음, n이상의 팰린드롬으로 구현되는 합의 개수를 저장하고 dp 때리면 될 거 같음. 증명은 업솔빙으로 한다 ㅅㅂ

[1052(182.231)]

배낭 dp맞음 근데 수를 여러번 쓸 수 있으니까 뒤에서부터가 아니라 앞에서부터 바텀업 처리해주면 됨 for(int i=0; i<=40000-x; i++) dp[i+x]+=dp[x] (for all x , x = palindrome)

[익명(219.254)]

하 시팔 ㅠㅠ

[익명(221.167)]

그게 어떻게 발상함? 팰린드롬 수를 다 구현했고, 4만 크기를 2차원으로 표현하면 16억이라 이 부분부터 꽉 막혔는데 ㅠㅠ

[1052(182.231)]

팰린드롬 개수가 500개니까 어떻게든 500*40000에 풀 생각을 해야되는데 16억으로 접근해서 막히는거지 dp문제를 많이 풀어보셈

[익명(123.109)]

식이 좀 이상한거 같음...

[익명(123.109)]

dp[0]=1 하고 dp[i+x] += dp[i] 인거 같음