목록2의 멱수의 합 C++ (1)

1일1알

백준 2410번 2의 멱수의 합 C++

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 숫자들의 순서가 다르더라도 같은 숫자로 취급하기 때문에 오름차순으로 정렬된 숫자들만 고려하였다. 2차원 dp테이블 dp[n+1][21]을 만들었다. n+1은 입력받은 숫자가 n이기 때문에 n까지 저장할 수 있고, 21은 2^20이 약 1000000이기 때문에 저렇게 설정하였다. dp[r][c]가 나타내는 값은 r의 숫자에서 2^c가 가장 마지막으로 오는 숫자들의 합의 개수라고 설정하였다. 예를 들어 4의 경우, dp[4][0]은 2^0은 1이기 때문에 1이 마지막으로 오는 경우는 1 + 1 + 1 + 1 하나만 존재하고, dp[4][1]은 2^1은 2이기 때문에 2가 마지막으로 오는 경우는 1 + 1 + 2 , 2 + 2 이렇게 두 개가 존재한다. dp[..
알고리즘 2021. 12. 2. 15:59
이전 Prev 1 Next 다음