dfs 알고리즘 문제이다.
날짜를 돌면서 상담을 선택하고 선택된 결과의 최대 값을 비교하여 가장 최대의 값을 출력하는 문제이다.
깊이 대신에 날짜라고 생각하면 된다. (depth -> day)
각 날짜 마다 상담의 걸리는 시간과 상담 비용을 배열에 저장한다.
그리고 그 상담을 했는지에 대한 여부인 visited 배열을 생성한다.
dfs 알고리즘 코드의 주석을 보면서 설명하겠다.
private static void dfs(int day) {
// 종료 조건으로 현재 날짜가 정해진 N 날짜를 넘었으면 종료한다.
if (day > N) {
// 정해진 상담들의 비용을 돌면서 합을 구해 현재 최대 값을 업데이트 한다.
int sum = 0;
for (int answer : answerArr) {
sum += answer;
}
MAX = Math.max(MAX, sum);
return;
}
// 현재 날짜부터 반복문을 돌아야 한다.
for (int i = day; i < N + 1; i++) {
// i가 다음 i로 넘어가면 다음 날로 넘어간것이므로 day도 i에 맞게 최신화 해준다.
day = i;
// 지금 생각해보면 visited 배열은 없어도 될 것 같다..
if (!visited[i]) {
// 현재 날짜에서 현재 날짜에 있는 상담을 했을 때 정해둔 N 날짜를 넘기면
// 현재 날짜에 있는 상담은 못하는 것이므로 바로 종료 시점으로 넘긴다.
if (day + dayArr[i] > N + 1) {
dfs(day + dayArr[i]);
} else {
// 현재 날짜의 현재 날짜에 있는 상담을 할 수 있으므로
// 상담 했다고 TRUE 표시하며
// 정답 배열에 상담 비용을 추가해준다.
visited[i] = true;
answerArr[day] = costArr[i];
// 현재 날짜 + 상담 소요 날짜를 다음 DFS에 넘겨준다.
dfs(day + dayArr[i]);
// 다시 돌아왔으면 선택했던 날짜의 상담의 상담비용을 0으로 초기화
answerArr[day] = 0;
visited[i] = false;
}
}
}
}public class bj14501 {
public static int N;
public static boolean[] visited;
public static int[] dayArr;
public static int[] costArr;
public static int[] answerArr;
public static int MAX = 0;
public static void main(String[] args) throws Exception {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
visited = new boolean[N + 1];
dayArr = new int[N + 1];
costArr = new int[N + 1];
answerArr = new int[N + 1];
for (int i = 1; i < N + 1; i++) {
String line = br.readLine();
String[] split = line.split(" ");
dayArr[i] = Integer.parseInt(split[0]);
costArr[i] = Integer.parseInt(split[1]);
}
dfs(1);
bw.write(MAX + "");
bw.flush();
bw.close();
br.close();
}
private static void dfs(int day) {
// 종료 조건으로 현재 날짜가 정해진 N 날짜를 넘었으면 종료한다.
if (day > N) {
// 정해진 상담들의 비용을 돌면서 합을 구해 현재 최대 값을 업데이트 한다.
int sum = 0;
for (int answer : answerArr) {
sum += answer;
}
MAX = Math.max(MAX, sum);
return;
}
// 현재 날짜부터 반복문을 돌아야 한다.
for (int i = day; i < N + 1; i++) {
// i가 다음 i로 넘어가면 다음 날로 넘어간것이므로 day도 i에 맞게 최신화 해준다.
day = i;
// 지금 생각해보면 visited 배열은 없어도 될 것 같다..
if (!visited[i]) {
// 현재 날짜에서 현재 날짜에 있는 상담을 했을 때 정해둔 N 날짜를 넘기면
// 현재 날짜에 있는 상담은 못하는 것이므로 바로 종료 시점으로 넘긴다.
if (day + dayArr[i] > N + 1) {
dfs(day + dayArr[i]);
} else {
// 현재 날짜의 현재 날짜에 있는 상담을 할 수 있으므로
// 상담 했다고 TRUE 표시하며
// 정답 배열에 상담 비용을 추가해준다.
visited[i] = true;
answerArr[day] = costArr[i];
// 현재 날짜 + 상담 소요 날짜를 다음 DFS에 넘겨준다.
dfs(day + dayArr[i]);
// 다시 돌아왔으면 선택했던 날짜의 상담의 상담비용을 0으로 초기화
answerArr[day] = 0;
visited[i] = false;
}
}
}
}
}
반례 목록
3
3 100
1 99
1 2
정답 : 101
-----------------------------------------------------------------------------------
4
3 1
1 100
2 100
1 1000
정답 : 1100
-----------------------------------------------------------------------------------
3
2 100
2 6
1 5
정답 : 105
-----------------------------------------------------------------------------------
3
2 10
5 20
1 10
정답 : 20
-----------------------------------------------------------------------------------
4
1 1
3 1
1 1
1 1
정답 : 3
-----------------------------------------------------------------------------------
5
4 10
2 9
2 3
2 2
3 100
정답 : 11
-----------------------------------------------------------------------------------
2
3 100
1 10
정답 : 10
-----------------------------------------------------------------------------------
7
3 10
5 20
1 10
2 20
4 15
2 10
2 200
정답 : 40
-----------------------------------------------------------------------------------
6
3 20
2 70
3 100
1 40
1 40
1 11
정답 : 161
-----------------------------------------------------------------------------------
5
1 6
3 9
3 6
4 9
1 1
정답 : 16
-----------------------------------------------------------------------------------
6
1 10
1 10
2 10
1 15
1 10
1 10
정답: 55
-----------------------------------------------------------------------------------
5
1 100
4 200
1 99
2 150
1 160
정답 : 359
가오리의 개발 이야기