Note: 해당 알고리즘은 java로 풀이되었습니다.
문제 분석
처음으로 D4 난이도를 한 번 풀어봤는데 굉장히 어려운 문제였습니다.
결국 혼자의 힘으로 풀지는 못하고 댓글에 있는 점화식을 보았는데
아직까지도 점화식이 이해가지 않는 상황입니다.
빠른 시일 내로 점화식까지 해석해서 업로드하겠습니다.
(꾸벅)
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
static int N;
static long[] select = new long[1001];
static long Ans, sum;
public static void main(String args[]) throws Exception {
System.setIn(new FileInputStream("res/은비의동전뒤집기.txt"));
Scanner sc = new Scanner(System.in);
int T;
T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
N = sc.nextInt();
Ans = 0;
sum = 0;
long a = Solution(N);
System.out.println("#" + test_case + " " + a);
}
}
private static long Solution(int num) {
if (num == 1) {
return 0;
}
if (select[num] != 0)
return select[num];
long ans = num / 2;
for (int i = 1; i < num; i++) {
ans = (ans*i)% 1000000007;
}
select[num] = (ans + num * Solution(num - 1)) % 1000000007;
return select[num];
}
점화식을 도출하는 것이 어렵지 점화식만 안다면 간단하게 DP로 풀 수 있는 문제였습니다.
해설은 점화식을 해석한 다음에 올리는 것으로…
후기
만약 코드를 다운 받고 싶다면 공유한 깃허브에 접속해주세요.
오류 지적, 질문, 더 나은 풀이는 언제든지 메일이나 댓글로 부탁드립니다.
감사합니다.