π [λ°±μ€μκ³ λ¦¬μ¦ νμ΄] Q.14501 ν΄μ¬ λ¬Έμ νμ΄
π λ¬Έμ
https://www.acmicpc.net/problem/14501
μλ΄μμΌλ‘ μΌνκ³ μλ λ°±μ€μ΄λ ν΄μ¬λ₯Ό νλ €κ³ νλ€.
μ€λλΆν° N+1μΌμ§Έ λλ λ ν΄μ¬λ₯Ό νκΈ° μν΄μ, λ¨μ NμΌ λμ μ΅λν λ§μ μλ΄μ νλ €κ³ νλ€.
λ°±μ€μ΄λ λΉμμκ² μ΅λν λ§μ μλ΄μ μ‘μΌλΌκ³ λΆνμ νκ³ , λΉμλ ν루μ νλμ© μλ‘ λ€λ₯Έ μ¬λμ μλ΄μ μ‘μλμλ€.
μλ΄μ μ μ ν νμ λ, λ°±μ€μ΄κ° μ»μ μ μλ μ΅λ μμ΅μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
π μ κ·Όλ²
Q.14501 ν΄μ¬ λ¬Έμ νμ΄μ λλ€.
ν΄μ¬νκΈ° μ κΉμ§ μ΅λ μμ΅μ ꡬνλ λ¬Έμ μ λλ€.
μλ΄ κ°λ₯ν λ μ§λ₯Ό μ λΆ νμνμ¬
μ΅λ μμ΅μ ꡬν μ μμ΅λλ€.
μ€λ μλ΄μ νκ±°λ λ΄μΌ μλ΄μ νλ κ²½μ°λ₯Ό μ¬κ·μ μΌλ‘ νμνμ¬
λͺ¨λ κ²½μ°μ μλ₯Ό κ΅¬ν΄ λ³Ό μ μμ΅λλ€γ £.
π» μ½λ
package problem.bfsdfs;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
public class Main_14501 {
static int N;
static int t[];
static int p[];
static int max = -1;
public static void main(String[] args) throws IOException {
input();
solve(1,0);
System.out.println(max);
}
public static void solve(int index, int value) {
if (index >= N+1) {
max = Math.max(max,value);
return;
}
if (index + t[index] <= N + 1) {
solve(index + t[index], value + p[index]);
}
solve(index+1,value);
}
public static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
t = new int[N+1];
p = new int[N+1];
for(int i=1; i<=N; i++){
String temp[] = br.readLine().split(" ");
t[i] = Integer.parseInt(temp[0]);
p[i] = Integer.parseInt(temp[1]);
}
br.close();
}
}