Dynamic Programming - 1002. 돌다리 건너기
private static int solution(int n) {
int[] arr = new int[n+1];
arr[0] = 1;
arr[1] = 2;
for(int i=2; i<n; i++) {
arr[i] = arr[i-1] + arr[i-2];
}
return arr[n-1];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(solution(n + 1));
}
static int[] dy;
public int solution(int n){
dy[1]=1;
dy[2]=2;
for(int i=3; i<=n+1; i++) dy[i]=dy[i-2]+dy[i-1];
return dy[n+1];
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
dy=new int[n+2];
System.out.print(T.solution(n));
}
해당 문제는 그래프의 Dynamic Programming(동적 계획법)
을 통해 풀 수 있다.
앞에서 풀이한 계단 오르기문제와 동일한 로직이다. 한가지 유의할 점은 모든 돌 다리 밟고,
다음 땅까지 밟아야한다는 점이다. 계단 오르기 풀이에서 주어진 계단에서 한 계단을 더하여
풀이하는 것과 같다. ( 상세 설명은 계단 오르기 문제 참고 )