문제에서 2가지만 생각하면 된다
1.완전탐색으로 모든 경우의 수 를 생각한다
2.다음요일을 찾는과정에서 지나온 요일을 생각해야한다(더해준다)
처음에 2번을 생각못해서 오래걸렸다...아무튼
코드 구현은 다음과 같다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] t, p;
static int start, n, result = Integer.MIN_VALUE;
static void dfs(int num, int num2) {
// num2의 합이 n을 초과 할 경우 리턴
if (num2 > n) {
return;
}
// num2의 합이 n일인 경우 포함시킨다.
if (num2 == n) {
result = Math.max(result, num);
}
// j = n일의 기간 중, 중간 부터 시작일이 되는 경우, 지난 일 수 를 받아온다
int j = start;
for(int i = start+num2; i < n; i++, j++) {
// 다음 날로 넘어가는 경우 j+1일을 포함시킨다
dfs(num + p[i], num2 + t[i] + j);
result = Math.max(result, num);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
t = new int[n];
p = new int[n];
for(int i = 0 ; i < n ; i++) {
st = new StringTokenizer(br.readLine(), " ");
t[i] = Integer.parseInt(st.nextToken());
p[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < n; i++) {
start = i;
dfs(0,0);
}
System.out.print(result);
}
}
다른 사람들 풀이를 보니
DP로 많이 푼 것 같다. 아래의 코드를 이용하면 된다.
(dp를 많이 풀어봐야겠다..)
//dp : N일에 얻을 수 있는 최대 수익
int[] dp = new int[n+1];
//점화식
//현재 날짜에서 소요 시간과 비용을 더해 dp에 저장한다.
//이후, 중복될 때 최대값을 넣는다.
//dp[i + t[i]] = max(dp[i + t[i]], dp[i] + p[i]);
// 0부터 시작(다음날로 넘어가는 경우임)
for (int i=0; i<n; i++) {
// 날짜가 범위를 넘어가지 않는 경우 최대값 찾기
if (i + t[i] <= n) {
// 현재날짜의 소요시간 dp[i+t[i]]에서의 비용 =
// Math.max(현재날짜의 소요시간 들어갈 비용, 현재 날짜 dp에서의(이전의) 비용 + 현재날짜 비용)
// 즉, dp에(날짜 + 소요시간이 중복될때) 비용을 중복해서 최대값을 만든다
dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
}
//현재 경우의 수가 0일 수 있기 때문에 이전의 최대값을 계속해서 넣어줌.
//해당 날짜에 일할 수 없다면, 이전까지 일한 최대 수당을 넣어주어야 한다.
dp[i+1] = Math.max(dp[i+1], dp[i]);
}
System.out.println(dp[n]);