[문제풀이] 10-02. 돌다리 건너기

인프런, 자바(Java) 알고리즘 문제풀이

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(동적 계획법)을 통해 풀 수 있다.
앞에서 풀이한 계단 오르기문제와 동일한 로직이다. 한가지 유의할 점은 모든 돌 다리 밟고,
다음 땅까지 밟아야한다는 점이다. 계단 오르기 풀이에서 주어진 계단에서 한 계단을 더하여
풀이하는 것과 같다. ( 상세 설명은 계단 오르기 문제 참고 )