비트필드를 이용한 다이나믹 프로그래밍 (1) 썸네일형 리스트형 [Python] 1562번 계단 수 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 23/12/05 비트마스킹을 이용한 DP를 연습하기 좋은 문제이다. 클래스 5에도 있으니, 비트마스킹에 대한 개념을 이해한 뒤에 조금 생각해보고 풀면 더욱 도움이 될 것 같다. 문제 접근 방식: 길이가 매우 긴 자리수를 가지고 있는 특정한 계단 수에 대한 경우의 수를 구하는 문제이다. 계단 수이긴 하지만, $0$부터 $9$까지의 모든 숫자를 써야 한다는 점이 다르다. 즉, 우리는 숫자의 사용 여부를 관리해야 할 필요성이 있다. 그걸 DP 배열에 넣고 관리하기에는 조금 까다로운 면이 있다. 이럴 때 비트마스킹을 이용할 수.. 이전 1 다음