[BOJ] 백준 [15989] 1,2,3 더하기 JAVA

https://www.acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

풀이

전형적인 dp문제이다. 우선 단순 노가다로 풀어보다가 3번쨰마다 규칙이 있을거라는 추측을해본다.

두번째마다 1씩 올라가는 걸 확인 할 수 있다.

이걸 점화식으로 세우면 다음과 같다.

 

import java.util.*;
import java.io.*;
 
public class Main{
    static int TC;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        TC = Integer.parseInt(br.readLine());
        dp = new int[10001]; dp[1] = 1; dp[2] = 2 ; dp[3] = 3;
        float cnt=6;
        for(int i=4;i<=10000;i++){
            cnt = cnt/2;
            dp[i] = dp[i-3] + (int)cnt;
            cnt = cnt*2;
            cnt ++;
        }
        while(TC-->0){
            int input = Integer.parseInt(br.readLine());
            System.out.println(dp[input]);
        }
    }
}

 

참고한 다른사람 풀이의 점화식

어떻게 이런걸 생각해내지 .. ? 역시 dp에 탁월한 사람은 달라도 뭔가 다른것 같다.