[backjoon]14501 퇴사 java

www.acmicpc.net/problem/14501

14501번: 퇴사

silver 4.

백트래킹으로 모든 경우의 수를 구해서 풀이하였다.

내가 헷갈려했던 것은 날짜 계산이었는데,

스케줄을 짜는 시점에서 마지막 날은 현재 날짜 + 기간이었는데 이 부분이 헷갈렸다.

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

class Main {
	static int N, max;
	static int[][] works;
	static boolean[] visited;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		works = new int[N][2];
		visited = new boolean[N];
		max = Integer.MIN_VALUE;
		for (int i = 0; i < works.length; i++) {
			st = new StringTokenizer(br.readLine());
			int days = Integer.parseInt(st.nextToken());
			int money = Integer.parseInt(st.nextToken());
			works[i] = new int[] {days, money};
		}
		
		dfs(0,0,0);
		System.out.println(max);
	}
	
	public static void dfs(int length, int startDay, int salary) {
		if(length == N) {
			max = Math.max(max, salary);
			return;
		}
		
		for (int i = startDay; i < N; i++) {
			if(visited[i] || length > i) continue;
			visited[i] = true;
			int period = works[i][0];
			int money = works[i][1];
			if(period +i <= N)	dfs(i + period, i + period, salary + money);
			else dfs(N,i+1,salary);
			visited[i] = false;
		}
	}	
}

 

백준에서 다른 사람 풀이 보니까

private static int go(int day) {
    if (day == N + 1) return 0;
    if (day > N + 1) return Integer.MIN_VALUE;
    if (d[day] != -1) return d[day];

    d[day] = Math.max(go(day + 1), P[day] + go(day + T[day]));
    return d[day];
}

이렇게 그냥 재귀를 이용해서도 풀었는데 반성하게 된다ㅜㅜ

정말 직관적이고 간결한 풀이 ㅠㅠ

출처 : www.acmicpc.net/source/27688979