::SemiColon;;

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 위의 문제는 계단수의 성질와 DP를 이용하여 푸는 문제입니다. 맨 앞자리는 0이 오지못한다는 주의할 점도 있습니다. 맨뒷자리에 따라 뒤에 올 수 있는 수가 정해져있습니다. 맨 뒷자리가 0: 1, 1: 0, 2, 2: 1, 3, ... 8: 7, 9, 9: 8 이렇게 됩니다. 즉 인접하는 수의 전단계 계단수를 더하면 현재의 계단수를 구할 수 있게되는것입니다. 점화식으로 작성해보자면 dp[i][j]: 길이가 i이고 마지막 수가 j인 계단수의 개수 j=0 이면 dp[i][0] = dp[i-1][1] j=9 이면 dp..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 이 문제의 푸는 방법을 먼저 말하자면 피보나치 배열과 똑같은 답이다. 이유는 n = 1일때 아래와 그림과 같이 2×1 하나로 되어 결과는 1이다. n = 2일때는 아래와 그림과 같이 2×1 2개, 1×2 2개로 조합하여 만들 수 있기에 결과는 2이다. n = 3일때는 두가지 경우로 나눌 수 있는데 왼쪽의 그림은 n = 2의 그림에 단지 2×1 1개만 붙인 것이다. 왼쪽의 그림은 n = 1의 그림에 단지 1×2 2개만 ..

https://www.acmicpc.net/problem/1003 피보나치 함수는 대표적인 다이나믹프로그래밍 문제이다. 피보나치 함수는 f(0) = 0, f(1) = 1, n>=2, f(n) = f(n-1) + f(n-2)의 꼴이다. 위의 문제는 0이 나오는 횟수와 1이 나오는 횟수를 출력하는 것이다. 따라서 n=0: {1,0} n=1: {0,1} n=2: {1,1} n=3: {1,2} n=4: {2,3} .... 이렇게 이어진다. 위의 순서를 보고 규칙을 찾으면 n=i: {i-1 의 첫번째 원소 + i-2 의 첫번째 원소, i-1 의 두번째 원소 + i-2 의 두번째 원소}이다. 따라서 이에 맞게 함수를 작성하면 pair fibo(int a) { if (dp[a] != make_pair(0, 0)) r..