문제링크

문제 링크

문제설명

입력

출력 예제는 문제 링크로~ (너무 많아요 ㅜㅜ)

설명

1. 제한사항에서 N의 크기가 저렇게나 작다면 완전탐색을 생각하고있자.
2. 그중에서 DFS로 풀었는데 DP 풀이도 있다고 한다.
3. DFS 기본 예제 문제같음!
4. 그러나.. 재귀에 취약한 나는 이것조차 좀.. 많이 오래 걸렸는데 최근에 재귀에 대한 감을 좀 잡기 시작했다.

조금 더 많은 문제를 풀어보자

어려운 문제일수록, 약한 부분일수록, 내 능력밖인것 처럼 느껴질수록 달려들어 풀어보자

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[] T;
	static int[] P;
	static boolean[] visited;
	static int answer;
	static int N;
	public static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		T = new int[N];
		P = new int[N];
		visited = new boolean[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());
		}		
	}
	public static void dfs(int now, int pay) {
		if(now >= N) 
		{
			answer = Math.max(pay, answer);
			return ;
		}
		
		if(now + T[now] <= N)
		{
			dfs(now + T[now], pay + P[now]);			
		}
		dfs(now + 1, pay);		
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		init();
		
		dfs(0, 0);
		
		System.out.println(answer);
	}
}