반응형
🔺 문제
🔺 코드
- 풀이1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import java.util.*;
import java.io.*;
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[] dp = new int[N + 1];
for(int i = 1 ; i <= N ; i++) {
if(i == 1 || i == 2 || i == 3) {
dp[i] = i;
} else {
dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
}
}
System.out.println(dp[N]);
}
}
|
cs |
✅ 해결 아이디어
✔ DP → 피보나치 수열
- 풀이2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import java.util.*;
import java.io.*;
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[] dp = new int[1_000_001];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for(int i = 4 ; i <= N ; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
}
System.out.println(dp[N]);
}
}
|
cs |
dp 사이즈를 N + 1로 했다간 런타임 에러 (ArrayIndexOutOfBounds)가 뜬다.
🔺 다른 풀이들
- 멋진 설명 과정과 코드... 항상 감사하는 중...
- Top-Down 방식도!
- 메모이제이션 설명 감사..
💬 느낀 점
흠... DP 문제가 이 정도 난이도로만 나와준다면 고마울텐데...
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
✔ 런타임 에러 부분
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1912번: 연속합 (0) | 2023.05.30 |
---|---|
[백준/JAVA] 9461번: 파도반 수열 (0) | 2023.05.30 |
[백준/JAVA] 9184번: 신나는 함수 실행 (1) | 2023.05.30 |
[백준/JAVA] 24416번: 알고리즘 수업 - 피보나치 수 1 (0) | 2023.05.30 |
[백준/JAVA] 1495번: 기타리스트 (0) | 2023.05.30 |