목록비트필드를 이용한 다이나믹 프로그래밍 (1)

dh_0e

[PS] 박성원 / C++ (백준 1086번)

비트마스킹을 활용한 dp 문제, 근데 이제 큰 수 % k를 곁들인 .. 시행 착오 vector > dp[][]로 선언을 하여 dp[i][j] = i개의 원소를 합쳤을 때, 마지막 원소에 j번째 원소를 삽입한 pair(first = 지금까지 삽입한 원소들의 비트마스킹, second = k로 나눈 나머지)를 삽입하는 것으로 점화식을 짰다.이 후에 말도 안 되는 메모리 초과를 보여주며 전처리 및 메모리도 줄인 후 진행했는데 여전히 답이 안 보였다. 해결 방안갈아엎었다. 점화식부터 다시 구상하니 dp[i][j] = 지금까지 사용한 원소를 마스킹한 값이 i, 나머지가 j인 수열의 갯수 로 풀 수 있었다.전처리 및 dp에 각각 하나씩 사용한 경우의 수 저장ten_mod에 10^l 들을 k로 나눈 나머지를 모두 구해..
알고리즘/Baekjoon 2025. 3. 25. 23:38
이전 Prev 1 Next 다음