자바(백준) 15991 1, 2, 3 더하기 6

오답 노트 & 새로 알게 된 점

문제 점화식은 구글링을 통해 알 수 있었다,, dp는 너무 어렵다,, 

초기값은 dp[0] ~ dp[5]까지 있었다.

여기서 dp[0]은 원래대로라면 0이지만, 위의 조건을 만족시키기 위해 1이라고 했다.

위의 조건을 만족시키기 위해 dp[0]을 1이라고 내 마음대로 설정해도 되냐고 물어보았다. 아무것도 안 더하는 방법이 있다고 생각하면 dp[0]은 1이 될 수 있다. 그래서 문제를 어떻게 설명하냐에 따라 풀이가 달라지는 것 같다.

 

---

 

코드

package Dynamic_Programming;
 
//BOJ 15991  1, 2, 3 더하기 6
 
import java.util.*;
 
public class BOJ15991 {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
 
        long dp[] = new long[100001];
 
        //조건을 충족시키기 위해 dp[0] = 1로 함
        //아무것도 안 더하는 방법이 있다고 생각
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 2;
        dp[4] = 3;
        dp[5] = 3;
 
        for(int i = 6; i < dp.length; i++){
            dp[i] = (dp[i - 6] + dp[i - 4] + dp[i - 2]) % 1000000009;
        }
 
        int test = s.nextInt();
 
        while(test-- > 0){
            int num = s.nextInt();
 
            System.out.println(dp[num]);
        }
    }
}