2018. 3. 20. 14:45, 알고리즘/BOJ
https://www.acmicpc.net/problem/5557
N이 작다면 O(2^N)으로 풀이가 가능할텐데 N이 꽤 큽니다. 대신 수식의 중간 계산 과정에서 0~20 사이의 값만을 가진다는 점을 이용해 D[i][j] : j번째 수까지 처리했을 때 값이 i인 경우의 수로 두고 DP 테이블을 채워나갈 수 있습니다.
'알고리즘 > BOJ' 카테고리의 다른 글
| [BOJ] 10835번: 카드게임 (4) | 2018.03.20 |
|---|---|
| [BOJ] 11049번: 행렬 곱셈 순서 (0) | 2018.03.20 |
| [BOJ] 1509번: 팰린드롬 분할 (0) | 2018.03.20 |
| [BOJ] 1036번: 36진수 (0) | 2018.03.16 |
| [BOJ] 2531번: 회전 초밥 (0) | 2018.03.15 |
| [BOJ] 2436번: 공약수 (0) | 2018.03.15 |
Comments
