ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Java 9461 파도반 수열
    PS 2023. 5. 22. 11:21

     

     

    풀이 : 
    dp문제는 sub문제들이 main 문제를 해결해주기 때문에 해당 규칙을 찾아내기 위해 수열을 나열해주었고 나열한 수열에서 i번째에 오는 수는 i-2 + i-3 이란 식을 도출해내었고 이를 memoization해주어 값들을 구한 뒤 입력받은 N을 출력해주었다. 

    int형으로 값을 받으면 사이즈가 초과되니 long형으로 받아주었다.

    

    처음엔 dp문제 푸는 게 너무 막막했는데 꾸준히 계속 풀다보니 요령이 조금 생기는 거 같아서 뿌듯했다.

    top-bottom, bottom-top 두가지 방식으로 풀어보았다.

     

     

     

    bottom-top

    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));
            StringBuilder sb = new StringBuilder();
            int n = Integer.parseInt(br.readLine());
    
            long[] dp = new long[101];
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 1;
    
            for (int i = 3; i <= 100; i++) {
                dp[i] = dp[i-2] + dp[i-3];
            }
            for(int i = 0; i < n; i++){
                int j = Integer.parseInt(br.readLine());
                sb.append(dp[j]).append("\n");
            }
            System.out.println(sb);
        }
    }

     

     

    top-bottom

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Main {
    
        static long[] dp;
    
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuilder sb = new StringBuilder();
            int n = Integer.parseInt(br.readLine());
    
            dp = new long[101];
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 1;
    
    
            for (int i = 0; i < n; i++) {
                int j = Integer.parseInt(br.readLine());
                sb.append(recur(j)).append("\n");
            }
            System.out.println(sb);
        }
        public static long recur(int index){
            if(index <= 2){
                return dp[index];
            }
            if (dp[index] == 0) {
                dp[index] = recur(index - 2) + recur(index - 3);
            }
            return dp[index];
        }
    }

    'PS' 카테고리의 다른 글

    Java 2667 단지번호붙이기  (0) 2023.05.26
    Java 1021 회전하는 큐  (0) 2023.05.22
    Java 1149 RGB거리  (0) 2023.05.13
    Java 1145 적어도 대부분의 배수  (0) 2023.05.11
    Java 2941 크로아티아 알파벳  (0) 2023.05.06
Designed by Tistory.