패스트캠퍼스 챌린지 33일차

동적 프로그래밍(Dynamic Programming) - 2 

 

 

계단 오르기 (BOJ 2579)

 1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한계단을 밟으면서 이어서 다음 계단이나

    다다음 계단으로 오를 수 있다.

 2. 연속된 세계의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.

 3. 마지막 도착 계단은 반드시 밟아야 한다.

 

완전 탐색 접근을 통해서 모든 경우를 직접 하나하나 찾으면 경우의수가 너무 많기 때문에 동적 프로그래밍

으로 문제를 나누어서 탐색한다.

 

문제 파티셔닝

 - 마지막에 1칸을 올랐을 경우

   => (i-1) 번째 직전에 (i-2) 번째 계단도 밟았는가? (연속된 세번 계단을 오를수 없기 때문)

 - 마지막에 2칸을 올랐을 경우

 

 

가짜문제 정의

 - 필요한 정보를 문제에 추가하기

 Dy[i][0] : i-1번째 계단은 밟지 않고, i번째 계단에 도착하며 얻는 최대 점수

 Dy[i][1] : i-1번째 계단은 밟고, i번째 계단에 도착하며 얻는 최대 점수

  => 모자란 정보는 Dy 배열을 추가하여 값을 넣는다.

 

구현

static void pro(){
	// 초기값 구하기
    Dy[1][0] =  0;
    Dy[1][1] =  A[1];
    
    if(N > 2){
    	Dy[2][0] = A[2];
        Dy[2][1] = A[1] + A[2];
    }
    
    // 점화식을 토대로 Dy 배열 채우기
    for(int i =3; i <= N; i++){
    	Dy[i][0] = Math.max(Dy[i-2][0] + A[i], Dy[i-2][1] + A[i]; //전에 계단을 올랐을 떄 한칸 전에서 올라옴
        Dy[i][1] = Dy[i-1][0] + A[i]; // 전에 계단에서 두칸 올라왔다
    }
    
    
    // Dy배열로 정답 계산
    int ans = Math.max(Dy[N][0], Dy[N][1])
    

}

 

계단 오르기 - 심화탐구(역추적, Backtrack)

 - Table을 채워 나갈때에 기록을 함께 한다면 실제 방법도 찾을 수 있다, 이를 역추적, Backtrack이라 한다

 

 

 

오르막 수 (BOJ 11057)

 - 각 자리가 오름차순을 이루는 수

 - 길이가 N인 수 중에서 오르막 수의 개수를 10,007로 나눈 나머지를 구하자. 수는 0으로 시작할 수 있다

  EX) 길이 1 : 0,1,2,3, ... 9 => 총 10개, 길이 2 : 00,01,02....99 => 총 55개

 

 청답의 최대치는 10,007로 나눈 나머지로 출력해야한다. => Integer로 계산해도 된다.

 

가짜문제 만들기

Dy[i][last] = 길이가 i 이며, last로 끝나는 오르막 수 의 개수

 EX) D[4][6] : 길이가 4이고 마지막 숫자가 6인 경우

 

파티셔닝

 - last숫자 직전에 숫자가 어떻게 끝나는지로 파티셔닝 한다

 

static void pro(){
	// 초기값 구하기
    for(int num = 0 ; num < 9; num++){
    	Dy[1][num] = 1;
    }
    
    // 점화식을 토대로 Dy 배열 채우기
    for(int len = 2; len <= N; len++){
    	for(int num = 0; len <= 9; num++){
    	// Dy[len][num] =??
        // prev : 마지막숫자 직전의 숫자
        	for(int prev =0; prev <= num; prev++){
        	Dy[len][num] += Dy[len -1][prev];
            Dy[len][num] %= 10007; // 중간에 10007로 나눠주어야 값을 미리 Integer범위로 가져간다
        	} 
    	}
    }
    
    // Dy배열로 정답 계산하기
    int ans = 0;
    for (int num=0; num<=9; num++){
    	ans += Dy[N][num];
        ans &= 10007;
    }
    

}

 

 

 

33일차 인증

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]