코딩고치

1. 문제 주소 11727번: 2×n 타일링 2 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 2xn 타일링 문제에서 2x2 타일이 추가되었다. 문제를 푸는 방식은 똑같다. 3. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace std; int d[1001]; int main(void) { int n; cin >> n; d[1] = 1; d[2] = 3; for (int i = 3; i

1. 문제 주소 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2. 문제 n을 입력받아 2xn크기의 직사각형을 만들고 그 사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 다이내믹 프로그램 문제이다. 사각형을 그려서 규칙을 찾고 코드를 작성하였다. n=3일 때부터 가장 오른쪽 사각형이 1x2 , 2x1일 때로 나누어서 분석하면 쉽게 규칙을 찾을 수 있다. 3. 소스 코드 1. Bottom-up 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace st..

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 N을 문제에서 주어진 3가지 연산을 가지고 1을 만들 때, 연산을 사용하는 횟수의 최솟값을 출력해야하는 문제이다. 다이나믹 프로그래밍 문제로 크기가 반복문을 이용하여 작은 문제부터 차례대로 풀어 나가는 Bottom-up 방식과 재귀함수를 이용하여 큰 문제를 작은 문제로 나누어서 푸는 방식인 Top-down방식으로 풀 수 있다. 1. Bottom-up 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include using namespace std; int arr[100001]; ..