[Algorithms] 백준 DP 문제모음 (bottom-up 유형)

# 이친수 (2193번)

1. 곱셈 연산이나, 덧셈 연산은 큰 수 끼리 연산 수행 시 overflow 가 발생할 수 있음을 유의!!!!! (매우매우 중요)

• 저번에도 당하고 또 당하는 단골문제...

import java.util.Scanner;

public class Main{
    // not starting with 0
    // no serial 1
    // how many binary with condition above, on size N

    // 1<=n<=90 => dfs... Time Complexity(2^90)
    // recurrence relation?
    // f(n) = f(n-2) (starting with 1)
    //        + f(n-3) (starting with 0)
    //        + f(n-4) (starting with 00) .........?
    // f(1) = 1, f(2) = 1, f(3) =2 , f(4) = 3, f(5)=5 ,f(6)=8
    // f(4) = 1 + 0 + f(2) !!!!!!!!!!?
    // f(4) = 1000,
    //        1010, f(2)
    //        1001, f(1)
    // f(5) = 10000,
    //        10100, 10101, (f(3))
    //        10010,(f(2))
    //        10001 (f(1))
    // f(6) = 100000,
    //        101000, 101010, 101001,(f(4))
    //        100100, 100101,(f(3))
    //        100010, (f(2))
    //        100001, (f(1))
    // .... f(n) = f(n-2)+f(n-3)+... + 1
    // .... f(n-2) = f(n-4) + f(n-5)+ ... + 1
    // dp(n) = dp(n-2) + f(n-3)+ f(n-2)
    // f(6) = f(4)_...f(1) + 1 = 8
    // f(7) = f(5)+...f(1) + 1 = f(5)+f(4) =13
    // f(8) = f(6)+...f(1) + 1 = (f5)+(f6) = 21
    // f(9) = f(7)+...f(1) + 1 = (f8)+(f7) = 34
    // f(10) = f(9)+f(8)  = 55
    public static long dp[];

    public static long f(int n){
        if(n==1 || n==2 ) return dp[n]=1;
        else if(n==3) return dp[n]=2;
        else if(dp[n]!=0) return dp[n];
        return dp[n]=f(n-1)+f(n-2);
    }
    
    // O(n^2)
    public static int getCount(int n){
        if(n <4){
            if(n == 3) return 2;
            return 1;
        }else{
            int sum=0;
            for(int i=n-2; i>=1; i--){
                sum+=getCount(i);
            }
            //f2, f1
            return sum+1;
        }
    }

    public static void printArr(int size){
        for(int i=0;i<=size;i++){
            System.out.print(dp[i]+" ");
        }
        System.out.println();
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        dp= new long[n+1];
        System.out.println(f(n));
//        printArr(n);

    }
}

---

# 연속합 (1912번)

1. 배열없이 하나의 단일 값을 dp 의 memoization 으로 사용

2. BufferedReader 사용하면, 메모리와 수행속도에 엄청난 차이가...!

import java.util.Scanner;

public class Main{

    static long[] arr;
    //serial sum maximum
    //1<= n <=100_000
    static long sum=0;
    static long best=0;

    //O(n^2)
    public static void sumOfSubset(int size){
        for(int i=0; i<size; i++){
            sum=Math.max(arr[i],sum+arr[i]);
            best=Math.max(best,sum);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new long[n];
        for(int i=0; i<n; i++){
            arr[i]=sc.nextInt();
        }
        /* BufferedReader 가 속도와 메모리에서 훨씬 성능을 압도한다.... 훔 ...
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        br.close();
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        */
        

        best = arr[0];
        sumOfSubset(n);

        System.out.println(best);
    }
}

---

# 쉬운 계단 수 (10844번)

1. 점화식찾아서 기뻐했는데 하하... 뺄셈이라 숫자가 커져서 MOD로 뭐 어쩌할 도리가없다...

  * MOD로 나눠서 리턴하는 경우 뺄셈이 절대 들어가면 안된다.

2. MOD로 나눠서 리턴하는 경우, 모두 덧셈으로 치환 해주자!

 

# 성공한 코드

• O(n) 이긴 하지만 뭔가 찝찝하다..
• 1등 코드를 보니, N이 최대 100밖에 되지 않아, 100*10 의 2차원 전역변수를 사용했다. (로직은 같다. 휴.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    //1<=N<=100
    //ans = ans % 1_000_000_000
    //01 (x)
    //10,12
    //21,23
    //32,34
    //43,45
    //...
    //87,89
    //98, -17 ... uhm.....
    //1~8 은 다음자리에 2개의 수를 뽑을 수 있고,
    //9는 다음자리에 1개의 수만 뽑을 수 있다.
    //010,012 (x)  = 2
    //101,121,123  = 3
    //210,212, 232,234 = 4
    //321,323, 345,343
    //767,765, 789,787 = 4
    //876,878, 898 = 3
    //989,987 = 2

    //N=4..
    //0101, 0121, 0123 (1로시작하는 경우의 수)
    //case 0 : 1*3(case1)+ =3 // 1*2(case9)
    //case 1 : 1*2(case0)+ 1*4(case2) =6
    //case 2 : 1*3(case1) + 1*4(case3) =7
    //case 3 : 1*4(case4) + 1*4(case2) = 8
    //case 4 : 1*4(case5) + 1*4(case3) = 8
    // ...
    //case 7 : 1*4(case6) + 1*3(case8) = 7
    //case 8 : 1*4(case7) + 1*2(case9) =6
    //case 9 : 1*3(case8) + // 1*2(case0)
    //대칭이네?

    static long[] CASE;
    static long[] copied_CASE;
    static long MOD = 1_000_000_000;
    static void CASE_UPDATE(){
        copied_CASE = CASE.clone();
        CASE[0] = copied_CASE[1];
        CASE[9] = copied_CASE[8];
        for(int i=1;i<=8;i++){
            CASE[i] = (copied_CASE[i-1]+copied_CASE[i+1]) % MOD;
        }
    }

    static void find(int n){
        for(int i=2;i<=n;i++){
            CASE_UPDATE();
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        CASE = new long[10];
        copied_CASE = new long[10];
        for(int i=0;i<10;i++){
            CASE[i]=1;
        }
        find(n);
        long sum=0;
        for(int i=1; i<10; i++){
            sum=(sum+CASE[i])%MOD;
        }

        System.out.println(sum);
    }
}

 

# 뺄셈이 섞여서 실패한 코드

/* 점화식 코드... MOD로 나눠서 내뱉는 값에 뺄셈이 들어가면 안된다... 절대아니된다...
static long[] dp;
static long[] CASE=new int[10];
static long[] copied_CASE=new int[10];
static long MOD = 1_000_000_000;

static void CASE_UPDATE(){
    	copied_CASE = CASE.clone();
        CASE[0] = copied_CASE[1];
        CASE[9] = copied_CASE[8];
        for(int i=1;i<=8;i++){
            CASE[i] = (copied_CASE[i-1]+copied_CASE[i+1]) % MOD;
        }
}

static void find(int n){
	for(int i=2;i<=n;i++){
    		dp[i] = ((dp[i-1]*2) - (CASE[0]))%MOD ;
        	CASE_UPDATE();
        }
}
 /*

---

# 1, 2, 3 더하기

1. d[n] = d[n-1] + d[n-2] + d[n-3] :  n에서 1을 뺀 경우, n에서 2를 뺀 경우, n에서 3을 뺀 경우 (첫 숫자로 1,2,3 을 선택한경우!)

import java.util.*;

public class Main {

    static int[] d;

    //dp
    public static int get(int n){
        //d[n+1] = d[n]+d[n-1]+d[n-2]
        if(n==0) return 0;

        if(n==1) return 1;
        else if(n==2) return 2;
        else if(n==3) return 4;
        else if(d[n]!=0) return d[n];

        return d[n]=get(n-1)+get(n-2)+get(n-3);
    }
    
    //dfs
    static int cnt=0;
    public static void dfs(int n){
        if(n==0) {
            cnt++;
            return;
        }else if(n<0) return;
        dfs(n-1);
        dfs(n-2);
        dfs(n-3);
    }

    public static void main(String[] args) {
        d=new int[50];
        
        Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt();
            System.out.println(get(n));   
        }
        
        /* dfs
        for(int i=0;i<t;i++){
            int n=sc.nextInt();
            dfs(n);
            System.out.println(cnt);
            cnt=0;
        }
        */
    }
}

---

# 카드 구매하기 (11052번)

1. Optimal 부분합 문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    static int[] cards;
    static int[] dp;
    //N : 카드팩 갯수
    //cards[i] : i개의 카드가 들어있는 카드팩의 가격
    //N개를 충족하는 최대 금액
    //1<=N<=1,000, 1<=cards[i]<=10,000

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        cards = new int[n+1];
        dp = new int[n+1];
        for(int i=1; i<=n; i++){
            cards[i]=Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<=n;i++){
            for(int j=1; j<=i;j++){
                dp[i] = Math.max(dp[i],dp[i-j]+cards[j]);
            }
        }

        System.out.println(dp[n]);
        
    }
}

---

# 이동하기 (11048번)

1. 오른쪽, 아래쪽, 대각선 방향을 다 고려했으나, 각 원소가 다 자연수이기 때문에, 대각선으로 오는걸 고려할 필요가 없었음...

  (합은 항상 거쳐서 오는게 더 크니까...) 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{

    static int[][] maze;
    static int[][] sum;
    static int n;
    static int m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        maze= new int[n+1][m+1];
        sum = new int[n+1][m+1];

        for(int i=1;i<=n;i++){
            st= new StringTokenizer(br.readLine());
            for(int j=1;j<=m;j++){
                maze[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        int max = 0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                sum[i][j] = maze[i][j]+Math.max(Math.max(sum[i-1][j],sum[i][j-1]),sum[i-1][j-1]);
                if(sum[i][j]>max) max=sum[i][j];
            }
        }
        System.out.println(max);
    }
}

---

# 피보나치 함수 (1003번)

import java.io.*;


public class Main{
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        dp = new int[41][2];
        dp[0][0]=1; dp[0][1]=0;
        dp[1][0]=0; dp[1][1]=1;

        for(int i=2; i<41; i++){ //40 까지 
            dp[i][0] = dp[i-1][0]+dp[i-2][0];
            dp[i][1] = dp[i-1][1]+dp[i-2][1]; 
        }


        for(int i=0; i<t; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n][0]+" "+dp[n][1]);
        }        
    }
}

---

# 가장 긴 감소하는 부분 수열 (11722번)

1. 최적 부분 구조에 해당한다 -> dp

2. dp[n] 의 정의를 내리는게 쉽지않았다. 최적 부분 구조에 해당하는게 return 값인데, 그러한 return 값을 위주로 dp[n]의 정의를 내려야 고생 안한다... 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class test{

    static int[] arr;
    static int[] dp;

    public static void printArr(int i, int j, int n){
        System.out.printf("# i=%d,j=%d : ",i,j);
        for(int k=0; k<n; k++){
            System.out.printf("%2d ",dp[k]);
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());

        dp = new int[n];
        arr = new int[n];

        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int result =0;
        for(int i=0; i<n; i++){
            dp[i]=1;
            for(int j=i-1; j>=0; j--){
                //여태 너보다 큰거 몇개있었어? 그 전 친구보다 많구나?
                if(arr[i]<arr[j] && dp[i]<=dp[j] ){
                    dp[i]=dp[j]+1;
                }
                // printArr(i, j, n);
            }
            result = Math.max(result, dp[i]);
        }
        System.out.println(result);
/*
7
30 29 31 28 6 10 5
*/
    }
}

---

# 가장 큰 증가 부분 수열 (11055번)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{

    static int[] arr;
    static long[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        arr = new int[n];
        dp = new long[n];

        for(int i = 0; i < n ; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //dp[n] : 수열의 증가 부분 수열중 합이 제일 큰 값 

        long result = 0;
        for(int i=0; i<n; i++){
            dp[i]+=arr[i];
            long memo=0;
            for(int j=i-1; j>=0; j--){
                if(arr[i]>arr[j] && dp[j]>memo ){
                    memo= dp[j];
                }
            }
            dp[i]+=memo;
            result = Math.max(result,dp[i]);
        }

        // for(int i=0; i<n; i++){
        //     System.out.printf("%3d ",dp[i]);
        // }
        // System.out.println();

        System.out.println(result);

    }
}

/*
7
5 50 20 100 101 30 500
 */

---

# 가장 긴 바이토닉 부분 수열 (11054번)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class test{

    static int[] arr;
    static int[] ldp;
    static int[] rdp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        arr = new int[n];
        ldp = new int[n];
        rdp = new int[n];

        for(int i = 0; i < n ; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //dp[n] : S(n)을 기준으로 바이토닉수열일 때, 가장 길이가 큰 값... 점화식을 못찾겠는걸 ㅎ...?
        //ldp[n] : 부분 증가수열이면서 길이 제일 큰 값
        //rdp[n] : 부분 감소수열이면서 길이 제일 큰 값 
        for(int i=0; i<n; i++){
            ldp[i]=1; 
            for(int j=i-1;j>=0;j--){
                if(arr[i]>arr[j] && ldp[i]<=ldp[j]){ // 증가수열 
                    ldp[i]=ldp[j]+1;
                }
            }
        }

        for(int i=n-1; i>=0; i--){
            rdp[i]=1;
            for(int j=i+1;j<n;j++){
                if(arr[i]>arr[j] && rdp[i]<=rdp[j]){ // 감소수열
                    rdp[i]=rdp[j]+1;
                }
            }
        }

        // for(int i=0;i<n;i++){
        //     System.out.printf("%2d ",ldp[i]);
        // }
        // System.out.println();

        // for(int i=0;i<n;i++){
        //     System.out.printf("%2d ",rdp[i]);
        // }
        // System.out.println();
        
        int result = 0;
        for(int i=0;i<n;i++){
            result = Math.max(result, ldp[i]+rdp[i]-1);
        }
        System.out.println(result);
    }
}

/*
10
1 5 2 1 4 3 4 5 2 1
 */

---

# 가장 긴 증가하는 부분 수열5 (14003번)

1. n과 arr[n]의 값이 +-10억 사이이다.

2. 시간복잡도는 binarySearch (LogN) * 메인 for문(N) => NLogN 이다.

3. C++과 다르게 Java는 바이너리서치를 직접구현해야하므로, 부등호와 리턴인덱스에 주의하자.

4. LIS 알고리즘의 원리가 기억안난다면, 꼭 검색해서 다시 익혀두자. (geeksforgeeks 추천)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main{
    static long[] arr;
    static long[][] dict;
    static long[] lis;

    static int binarySearch(int start, int end, long target){
        while(start<end){
            int mid = (start+end)/2;
            if(lis[mid] <  target){
                start = mid+1;
            }else{
                end=mid;
            }
        }
        
        return end;
    }

    static void printArr(long[] arr, int n){
        for(int i=0;i<n;i++){
            System.out.printf("%2d ",arr[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        arr = new long[n];
        dict = new long[n][2];
        lis = new long[n];

        for(int i = 0; i < n ; i++){
            arr[i] = Long.parseLong(st.nextToken());
        }

        //dp[n] : 수열의 증가 부분 수열중 합이 제일 큰 값 

        int top=0; int len = top+1;
        lis[0] = arr[0];

        int dictIdx=0;
        dict[dictIdx][0] = len;//len
        dict[dictIdx++][1] = lis[top];  //value

        for(int i=1;i<n;i++){
            if(lis[top] < arr[i]){  
                lis[++top] = arr[i];
                len=top+1;
                dict[dictIdx][0] = len;
                dict[dictIdx++][1] = lis[top];
            }
            else{
                int idx = binarySearch(0, top ,arr[i]);
                lis[idx]=arr[i];
                dict[dictIdx][0]=idx+1;
                dict[dictIdx++][1]=lis[idx];
            }

            // printArr(lis, n);
        }

        System.out.println(top+1);

        len = top+1;
        long[] stack = new long[len];
        int cnt=0;
        for(int i=dictIdx-1;i>=0;i--){
            // if(len==0) break;
            if(dict[i][0] == len){
                stack[cnt++]=dict[i][1];
                len--;
            }
        }


        len =top+1;
        // for(int i=0; i<len; i++){
        //     System.out.println(stack[i]);
        // }

        for(int i=len-1;i>=0;i--){
            System.out.print(stack[i]+" ");
        }
    }
}

/*
7
5 50 20 100 101 30 500

11
50 29 30 31 14 24 32 33 34 25 29

8
1 6 5 7 8 1 2 3
 */

---

# 설탕배달 (2839번)

1. 이걸 어떻게 dp로 풀지..? 😢

2. 구글링해서 dp 풀이법을 찾았다..! 이해는 되는데, 어떻게 저게 직관적으로 떠오르는 걸까... 🧐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int kg = Integer.parseInt(br.readLine());

        //5kg, 3kg
        int _5kg = kg/5;
        int res = kg-_5kg*5;

        //gready
        while(true){
            if(res%3==0 || _5kg==0) break;
            _5kg-=1;
            res=kg-_5kg*5;
        }
        
        if(res%3!=0) System.out.println(-1);
        else{
            int _3kg = res/3;
            // System.out.println(_5kg+" "+_3kg);
            System.out.println(_3kg+_5kg);
        }
    }
}

// DP 풀이법
// https://jhhj424.tistory.com/40
/*
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n<5) {
            if(n==3) System.out.println(1);
            else System.out.println(-1);
            return;
        }
        int dp[] = new int[n+1];
        Arrays.fill(dp, 9999);
        dp[3] = 1;
        dp[5] = 1;
        for(int i=6; i<dp.length; i++) {
            dp[i] = Math.min(dp[i-3]+1, dp[i-5]+1);
        }
        if(dp[n] > 9999) {
            System.out.println(-1);
        }else {
            System.out.println(dp[n]);
        }
    }
}
*/

---

# 정수 삼각형 (1932번)

1. triArr 안쓰고 dp 배열만으로도 답을 구할 수 있다. (n^2 의 공간복잡도는 아깝긴하다.)

2. 1차원배열로 dp 배열이나 triArr 배열을 선언한다면 공간복잡도는 n이 된다. (offset, strides가 귀찮다) (시간되면 해볼 것)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int triArr[][] = new int[n][n];
        int dp[][] = new int[n][n];
        int result=0;
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<i+1;j++){
                triArr[i][j]= Integer.parseInt(st.nextToken());
                if(i>0){
                    if(j==0) {
                        dp[i][j]=dp[i-1][j]+triArr[i][j];
                        continue;
                    }
                    dp[i][j]=Math.max(dp[i-1][j-1],dp[i-1][j])+triArr[i][j];
                }else{
                    dp[i][j] = triArr[i][j];
                }
                result=Math.max(result, dp[i][j]);
            }
        }

        System.out.println(result);

        // for(int i=0; i<n; i++){
        //     for(int j=0; j<n; j++){
        //         System.out.printf("%2d ", triArr[i][j]);
        //     }
        //     System.out.println();
        // }

        // System.out.println("# dp");
        // for(int i=0; i<n; i++){
        //     for(int j=0; j<n; j++){
        //         System.out.printf("%2d ", dp[i][j]);
        //     }
        //     System.out.println();
        // }



    }
}

---

# 01타일 (1904번)

1. 진짜진짜진짜진짜 점화식 찾는게 세상에서 가장 어렵따... 🤯

2. 곱셈은 언제나 오버플로우의 단골손님이지... 덧셈도 터지는데 말이야.. -> 점화식 잘못찾았다는 소리

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //ans = ans % 15746 
        int mod = 15746;

        //size 2(bianry 0), 1(binary 1)
        //n==2 / 00 11
        //n==3 / 001 100 111
        //n==4 / f(3) 1001 1100 1111 / f(2) 0000 0011
        //n==5 / f(5) = (f(4)-1)*2  (00들어간거 앞뒤로 1붙일때)
        //               +1         (1로만 이뤄진거 1붙일때)
        //            = 2f(4) -1 = 2f(3)+2f(2) -1
        // 아근데... 곱셈... 들어가면..........  숫자커지면 오버플로우생기는데 ㅠㅠㅠㅠ
        
        // f(1) = 1, f(2) = 2, f(3) =3, f(4)=5
        // f(5) = 8
        // f(6) = 13
        // 헤헷,, 점화식을 잘못찾았구만

        long dp[]= new long[n+1];
        
        //least exception handling
        if(n==1) {
            System.out.println(1);
            return;
        }

        dp[1]=1; dp[2]=2; 
        for(int i=3; i<=n; i++){
            dp[i]= (dp[i-2]+dp[i-1])%mod;
        }

        System.out.println(dp[n]);
    }
}