• 중복 조합 구현
  • 방문 여부를 현재 cnt에 해당하는 sum의 방문 여부로 정의했고, 2차원으로 구현


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



import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int[] num = {1, 5, 10, 50};
	static boolean[][] visited;

	static void go(int cnt, int start, int sum) {
		if (cnt >= N) {
			visited[sum][cnt] = true;
			return;
		}
		if (visited[sum][cnt]) return;
		visited[sum][cnt] = true;
		for (int i = start; i < 4; i++)
			go(cnt+1, start, sum + num[i]);
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		visited = new boolean[1001][N+1];
		
		go(0, 0, 0);

		long res = 0;
		for (int i = 1 ; i < 1001; i++)
			if (visited[i][N]) res++;
		System.out.println(res);
	}
}