길이가 N인 문자열이 있습니다.
문자열은 문자 A B C D로 이뤄져 있습니다.
문자 A B C D는 각각 1 5 10 50으로 매칭됩니다.
문자열이 의미하는 수가 각 문자가 매칭된 수의 총합일 경우
길이 N이 주면 표현될 수 있는 수의 경우의 수를 구해야 합니다.
1 이면 1 5 10 50
2 이면 2 6 10 11 15 20 51 55 60 100 이런식으로요.
저는 그래서 동적 계획법으로
D(i) = D-1(i-1) + D-1(i-5) + D-1(i-10) +D-1(i-50) 을
N번 수행하여
로 O(N)으로 해결하고자 했는데
답이 안나와서 도움을 요청드립니다.
문자열은 문자 A B C D로 이뤄져 있습니다.
문자 A B C D는 각각 1 5 10 50으로 매칭됩니다.
문자열이 의미하는 수가 각 문자가 매칭된 수의 총합일 경우
길이 N이 주면 표현될 수 있는 수의 경우의 수를 구해야 합니다.
1 이면 1 5 10 50
2 이면 2 6 10 11 15 20 51 55 60 100 이런식으로요.
저는 그래서 동적 계획법으로
D(i) = D-1(i-1) + D-1(i-5) + D-1(i-10) +D-1(i-50) 을
N번 수행하여
로 O(N)으로 해결하고자 했는데
답이 안나와서 도움을 요청드립니다.
- dc official App
N 범위가?
20까지입니다 - dc App
백준 문제인데 문제번호는 16922 입니다 - dc App
N=20이면 만들 수 있는 수가 기껏해야 1000인데 다해보면 되지
1~1000까지 일일히 확인해보는건 N개의 숫자조합을 계속 탐색해야되서 동적 계획법으로 1~1000까지 만들어지는 수 개수를 구하고 거기서 노출된 수의 경우만큼만 카운트할 생각을 하였습니다 - dc App
근데 틀려서 생각이 잘못된건가 여쭤보았습니다 ㅜ.ㅜ - dc App
지금 님이 하는 dp로는 숫자 배열이 바뀌면 다른걸로셈
헉 그런가요? 1 10 1 과 1 1 10을 다른 경우로 센다는 말씀이신거죠? - dc App
ㅖ
아 네 맞습니다. 그래서 DP결과를 더하는게 아니라 DP N회가 끝나면 -1이 아닌 수들을 카운트 하려고 했어요 - dc App
1번 인덱스가 1~N깊이 , 2번 인덱스가 1~1010범위인 2차원 배열로요 - dc App
? 저식대로 짜면 맞지않나
bool dp[i][j] = i개 이하의 문자로 j를 만들 수 있는가? 해서 sum(dp[N][...]?1:0) 여기서 1차원 줄여도되고
이렇게 짜려면 저 식의 + 가 or로 바뀌어야함
dp[i][j] = dp[i-1][j] || dp[i-1][j-1] || dp[i-1][j-5] || dp[i-1][j-10] || dp[i-1][j-50] ㅇㅋ?
Yup
아 감사합니다 결국 시아닌님 의견에 도움을 얻은게 생각없이 int32로 DP배열 돌렸다가 19->20번째 인덱스에서 값 일부가 오버플로우나서 카운팅을 못하게 되었네요 ㅋㅋ 논리형으로 전환해서 해결하였습니다요~ - dc App
두분다 정말 감사합니다!! - dc App