[백준/JAVA] 1904번: 01타일
🔺 문제
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
🔺 코드
- 풀이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)가 뜬다.
🔺 다른 풀이들
- 멋진 설명 과정과 코드... 항상 감사하는 중...
[백준] 1904번 : 01타일 - JAVA [자바]
st-lab.tistory.com
- Top-Down 방식도!
[알고리즘 PS] 백준 1904번 01 타일 자바 문제 풀이
문제 해당 포스팅은 백준의 1904번 01 타일 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 문제 해결법 우선 문제를 제대로 파악해보자.
wonit.tistory.com
- 메모이제이션 설명 감사..
[백준][JAVA알고리즘]1904번 풀이(01타일) - 초보도 이해하는 풀이
안녕하세요 인포돈 입니다. 백준 알고리즘 1904번 풀이입니다. * 참고사항 - 개발환경은 eclipse을 기준으로 작성되었습니다. - java언어를 이용하여 문제를 풀이합니다. - 알고리즘 문제는 풀이를 보
infodon.tistory.com
💬 느낀 점
흠... DP 문제가 이 정도 난이도로만 나와준다면 고마울텐데...
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V |
(참고)
✔ 런타임 에러 부분
글 읽기 - 자바 런타임 에러
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net