고민하다가.. Pekaz 고민하다가 .. 힌트 좀 얻고자 질문을 올립니다 ㅠㅠ 확실히 안하니까 실력이 줄어드는 감이 팍팍 - 으아ㅏㅏ아아- (물론 이 문제는 codeforces 에서 나온거지만 해당 contest는 이미 끝났으므로 ..) 문자열이 한개 주어집니다. (길이는 최대 1500 , 소문자만 들어옴) 그다음으로 26개의 0 또는 1이 주어집니다. 각 0 과 1의 의미는 i 번째 숫자가 0 이면 i번째 알파벳이 bad word i 번째 숫자가 1 이면 i번째 알파벳이 good word 입니다. 그리고 세번째 줄에는 숫자가 하나 주어집니다. 해당 숫자는 bad word 의 허용갯수 입니다. 여기서 이 문제의 목표는 첫번째 줄에 주어진 문자열에서 부분 문자열이 몇개인지 세는 것 입니다. 하지만 그 부분문자열에 bad word는 허용갯수 이하로만 포함되어야 합니다. 그리고 중복된 부분문자열은 한개로 셉니다. 다시 말해서 bad word 를 허용치 이하로 포함하는 부분문자열들의 union 을 구하라. 입니다. 입력예로는 ababab 01000000000000000000000000 1 출력예는 5 입니다. ("a", "ab", "b", "ba", "bab". 이렇게 5가지) 음 .. 두세시간동안 고민했었는데 .. 뭔가 어렵지 않은거 같은데 .. 갈피를 못 잡겠어서 이렇게 남겨요 ㅠ 힌트좀 부탁드립니다 (...) 으아아 연습이 시급합니다- 11년 전
6개의 댓글이 있습니다. Pekaz 문제 원문 http://www.codeforces.com/problemset/problem/271/D 11년 전 link VOCList 1500이니까 모든 substring에 대해서 trie를 만들어보면 해결할 수 있을 것 같아요. 11년 전 link Pekaz 으헉 .. ? 그래요 ? 공간복잡도 때문에 살짝 trie 는 안될것 같았는데 .. 한번 생각해볼게요 11년 전 link hyunhwan 어차피 trie를 만든다 하더라도 공간 복잡도는 넉넉하게 잡아도 O(N^2) 정도가 될 터인데(N = 문자열의 길이). 1500 * 1500 = 2250000 정도면 충분할꺼 같은데요. 11년 전 link Pekaz Trie 개념은 알겠는데 직접 문제에 적용을 안해봐서 그런지 감이 안잡히네여 ...으아 11년 전 link Pekaz 엇 종만북 781쪽 Yeahh! 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Pekaz
고민하다가 ..
힌트 좀 얻고자 질문을 올립니다 ㅠㅠ
확실히 안하니까 실력이 줄어드는 감이 팍팍 - 으아ㅏㅏ아아-
(물론 이 문제는 codeforces 에서 나온거지만 해당 contest는
이미 끝났으므로 ..)
문자열이 한개 주어집니다. (길이는 최대 1500 , 소문자만 들어옴)
그다음으로 26개의 0 또는 1이 주어집니다.
각 0 과 1의 의미는
i 번째 숫자가 0 이면 i번째 알파벳이 bad word
i 번째 숫자가 1 이면 i번째 알파벳이 good word 입니다.
그리고 세번째 줄에는 숫자가 하나 주어집니다.
해당 숫자는 bad word 의 허용갯수 입니다.
여기서 이 문제의 목표는
첫번째 줄에 주어진 문자열에서 부분 문자열이 몇개인지 세는 것
입니다.
하지만 그 부분문자열에 bad word는 허용갯수 이하로만 포함되어야
합니다.
그리고 중복된 부분문자열은 한개로 셉니다.
다시 말해서
bad word 를 허용치 이하로 포함하는 부분문자열들의 union 을 구하라.
입니다.
입력예로는
ababab
01000000000000000000000000
1
출력예는
5
입니다. ("a", "ab", "b", "ba", "bab". 이렇게 5가지)
음 .. 두세시간동안 고민했었는데 .. 뭔가 어렵지 않은거
같은데 .. 갈피를 못 잡겠어서 이렇게 남겨요 ㅠ
힌트좀 부탁드립니다 (...)
으아아 연습이 시급합니다-
11년 전