인문학적 공학도

불러오는 중입니다... 상당히 간단한 풀이의 문제였다. 일단 N과 K를 아무 숫자나 정하고 차근차근 세어보기로 한다. (10,K)로 대충 정해보자 N=10 K=1: 1개 N=10 K=2 : (0,10), (1,9), (2,8) ... (10,0) 11개 N=10 K=3 : (0,0,10), (0,1,9) ... (0,10,0) / (1,0,9), (1,1,8) ... (1,9,0) / ..... / (10,0,0) N=10 K=3에서 붉은 색 부분을 보자. N=10 K=2일 때의 경우의 수 그대로다. 주황 색 부분은? N=9 K=2일 때의 경우의 수이다. 쭉 진행해보면 마지막 파란색 부분은 N=0 K=2일 때의 경우의 수다. 간단하게 점화식을 얻을 수 있다. (N,K)=(N,K-1)+(N-1,K-1)+...

11727번: 2×n 타일링 2 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. www.acmicpc.net DP문제를 연습하고 있다만 설명의 과정이 귀찮아 블로그에 기록하진 않았다. 이번 문제는 설명하기가 간단하고, DP의 핵심적인 부분을 다루고 있다. 블럭이 한 칸(2x1) 증가하는 경우와 두 칸(2x2)씩 증가하는 경우, 2가지를 상정한다. 이 때 두 칸씩 늘어나는 경우는 가로로 누운 블럭 두 개가 붙은 경우와 큰 하나의 블럭, 두 가지 블럭이다. 길이i 타일 = 길이가 i-1인 타일에 한 칸을 붙인 경우(경우의 수는 그대로) + 두 칸씩 늘어나는 경우*2(두 가지 블럭) 점화식으로 표현하면 DP[i] = DP[i-1] + DP[i-2]*2 #inclu..