-
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