백준 알고리즘/Dynamic Programming2 백준 20500번 - Ezreal 여눈부터 가네 ㅈㅈ https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명이 아주 깔끔해서 맘에 드는 문제다. 1과 5로만 구성된 n자리의 수가 15의 배수가 되는 경우의 수를 구해야 한다. 15는 3*5이므로 15의 배수는 5,0으로 끝나면서 자릿수의 합이 3의 배수여야한다. 즉 이 문제의 경우에는 1의 자릿수가 5가 되면서 총 자릿수들의 합이 3의 배수가 되면 된다. 자릿수가 3의 배수가 되는 경우에 한해 5151515, 1111115 같은 경우의 수를 계산해줘야 한다. 1의 자릿수는 5 고정이므로 앞의 n-1개의 자리에 5가 어디어디에 들어갈지 고려.. 2021. 10. 4. 백준 14852번 - 타일 채우기(3) https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net DP문제의 기본형에서 1*1의 타일이 생기면서 조금 더 생각을 할 필요가 있는 문제였다. 원래는 간단하게 DP[i]=DP[i-1]+DP[i-2] 의 형식으로 해결이 가능하지만, 1*1의 경우가 생김으로써 DP[i]=DP[i-1]*2 + DP[i-2]*3 의 경우를 생각해야 한다. ㅁㅁㅁㅇ ㅁㅁㅁ| ㅁㅁ-- ㅁㅁ-- ㅁㅁㅇㅇ ㅁㅁㅁㅇ ㅁㅁㅁ| ㅁㅁ-- ㅁㅁㅇㅇ ㅁㅁ-- 여기에 밑에 경우를 생각해 줘야 한다. 즉, DP[i-3]*2의 경우, DP[i-4]*2의 경우, ... , D[0]*2의 경우를 생각해줘야.. 2021. 10. 4. 이전 1 다음