https://www.acmicpc.net/problem/1279
문제요약
- 6면의 주사위, 각 면의 숫자가 다름
- 평균이 M이 안 넘도록 하는 경우의 수(1 ~ 1000000)
접근법
- DP로 해결했는데 기억이 잘 안나서 단서만 적어봄
- 합 = M * 6
- 서로 다른 6개 숫자 조합으로 만들 수 있는 주사위 경우의 수 30 => 답과 30배 차이가 나서 30이라는 숫자를 얻은 것 같음
- dp : [구하려는 합][면의 수]
- 면의 수가 1이면 구하려는 합만큼 경우의 수가 될 것임
- [v][x] = [v - x][x - 1] + [v - (x + 1)][x] 점화식을 세웠는데 이유가 생각 안남
복기 1
- 면이 x개이고 채울 수 있는 합이 v일때
- 최저 숫자는 1, 2, 3, 4, ...가 될 수 있음
- 최저 숫자를 k라고 가정하면(k >= 1)
- 모두에서 1을 빼면 v - x, 면의 개수는 x
- 모두에서 2를 빼면 v - 2x, 면의 개수는 x
- k - 1을 빼면 v - 2(k- 1), 면의 개수는 x
- k 를 빼면 v-2k, 면의 개수는 x - 1(왜나면 0이 된 면은 더이상 고려하지 않아도 됨)
- 이들의 합이 최저 숫자 K일때의 경우의 수
- 1 ~ k까지의 모든 경우의 수를 더해서 합한다.
- [v][x]를 채우기 위해
- 1 ~ k까지 연산을 하는데
- k를 채우기 위해 1 ~ k까지 연산을 함
- 이제 루프를 최적화하면 실마리가 보일 것 같다.
newbieski