전체 글108 백준 11727 : 2xn 타일링2 문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 구현 방법 위의 계산을 통해 dp[N] = dp[N-2]*2 + dp[N-1] 임을 알 수 있습니다. 10007로 나눈 나머지를 출력해줘야 되기 때문에 dp에 값을 저장할 때부터 나눈 값을 저장해줍니다. 출력할 때 나누어 주면 수가 int 범위를 넘어서기 때문에 미리 저장하여 나눠줍니다. 구현 코드 package BOJ.Silver.dp; import java.io.BufferedReader; import java.io.IOExcept.. 2021. 3. 20. 백준 1932번 : 정수 삼각형 문제 www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 구현 방법 dp로 구현하였습니다. 각 삼각형 레벨에서 제일 왼쪽, 제일 오른쪽은 더해올 값이 하나이지만 중간의 값들은 왼쪽 위, 오른쪽 위 두 가지를 선택할 수 있으므로 두 가지 값 중 더 큰 값을 저장해줍니다. dp를 2차원 배열로 선언하여 왼쪽부터 인덱스를 주었을 때 같은 위치에 있는 윗 레벨 값을 현재 위치와 더하여 dp에 저장해줍니다. 만약 중간에 있는 값이라면 다음 인덱스의 값과 현재 위치와 더한 값, dp에 있는 값을 비교하여 더 큰 값을 저장해줍니다. 구현 코드 p.. 2021. 3. 19. 백준 1904번 : 01타일 문제 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 구현 방법 dp로 구현하였습니다. N을 구했을 때 N이 1일 때 1, 2일 때 2, 3일 때 3, 4일 때 5, 5일 때 8 .. 이므로 dp[n] = dp[n-2]+dp[n-1]이 점화식임을 알 수 있습니다. 주의할 점은 출력이 N의 개수가 아니라 15746을 나눈 나머지를 출력해야하므로 dp를 저장할 때 아예 나눠주었습니다. 구현 코드 package BOJ.Silver; import java.io.Buffe.. 2021. 3. 19. 백준 1463번 : 1로 만들기 문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 구현 방법 dp로 풀어주었습니다. 1부터 시작하여 횟수의 최솟값을 구해주었습니다. 모든 값이 할 수 있는 연산인 -1을 dp 에 넣고 /2가 가능하면 /2의 값과 현재 -1을 한 dp 값을 비교하여 더 작은 값을 dp에 넣어줍니다. /3도 마찬가지로 비교하여 더 작은 값을 dp에 넣어줍니다. 구현 코드 package BOJ.Silver; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import jav.. 2021. 3. 19. 이전 1 ··· 12 13 14 15 16 17 18 ··· 27 다음
