오늘의 키워드
•
동적 프로그래밍(DP)
•
메모이제이션
문제 파악 및 풀이
•
해당 문제는 보자마자 메모이제이션을 사용해야겠다고 생각했다
풀이 코드
import java.util.Scanner;
class Main {
public static final int MAX_N = 116;
public static long[] memo = new long[MAX_N + 1];
public static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
memo[1] = 1;
memo[2] = 1;
memo[3] = 1;
System.out.println(solve(n));
}
public static long solve(int x) {
if (memo[x] != 0)
return memo[x];
return memo[x] = solve(x - 1) + solve(x - 3);
}
}
Java
복사
오늘의 회고
어려웠던 점
1.
자료형 범위를 고려하지 않아 초기에 틀린 점이 아쉬웠다.
2.
메모이제이션 로직 자체는 어렵지 않았지만, 자료형 선택의 중요성을 느꼈다.
개선점
1.
다음부터 문제를 풀기 전에 최대 출력값의 크기와 자료형의 범위를 항상 체크하자.
2.
자료형을 선택할 때 신중하게 접근하는 습관을 길러야겠다.