문제 백준 5052번 풀이 문자열 $ A $가 다른 문자열의 접두사인지 빠르게 확인해야 합니다. 입력 받은 전화번호를 모두 정렬해봅시다. 911 97625999 91125426 이 케이스를 정렬하면 911 91125426 97625999 이렇게 됩니다. 여기서 관찰할 수 있는 것은, 문자열 $ A $가 임의의 문자열 $ B $의 접두사가 된다면, 그러한 문자열 $ B $는 항상 $ A $ 바로 뒤에 있다는 것입니다. 이 말이 이해가 안된다면 사전을 생각해봅시다. "abcd", "abcde"와 같은 단어가 있다고 가정합시다. 이를 사전순으로 배열하면 "abcd"까지 같으니 더 긴 문자열이 뒤로 오게 됩니다. 그렇게 뒤에 온 문자열은 항상 앞의 문자열을 접두사로 포함하고 있는 꼴이 될 것 입니다. 마지막으로..

문제 백준 5550번 풀이 전형적인 DP (누적합+그리디) 문제로 볼 수 있습니다. "dp[i] = i권을 선택했을 때 만들 수 있는 최대 가격" 으로 점화식을 세워줍시다. 모든 장르에 대해서 i번째 책까지 골랐을 때, 해당 장르의 j개의 책을 추가로 고르는 경우로 DP table을 채워주면 됩니다. 시간복잡도는 $ O(GN^2) $이 되는데, N이 1000이고 G가 10이므로 G는 무시할만한 수준입니다. 따라서, DP의 시간복잡도는 $ O(N^2) $이 됩니다. DP의 조건이 좀 까다로워 구현하는데 고생했던 것 같습니다. 소스코드 #include using namespace std; int dp[2001]; vector book[11], sum[11]; int main() { cin.tie(0)->sy..