문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 풀이 문제는 시작점부터 도착점까지 도달 가능한 경로 수를 구하는 것이다. 처음엔 DFS로 시도했지만 시간초과가 발생하여 반복문과 DP를 활용한 풀이를 하였다. 시작점인 dp[0][0]에 1을 할당하고, 반복문을 통해 각 위치까지의 도달 가능한 경로 수를 구한다. dp[i][j]가 0인 배열은 처리하지 않고 넘어가도록 하며 0이 아닌 경우에는 오른쪽과 아래 방향으로 map[i][j]만큼 이동 한 후, 그 지점의 dp 배열에 현재 위치 경로 수를 더..

문제 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 먼저 타일들을 나열해 보자. N = 1 / 1 N = 2 / 00, 11 N = 3 / 001, 111, 100 N = 4 / 0000, 1100, 0011, 1111, 1001 N = 5 / 00001, 11001, 00111, 11111, 10011, 00100, 11100, 10000 타일의 가짓수는 1, 2, 3, 5, 8개로 증가하며 피보나치 수열의 패턴을 보이고 있다. 따라서 dp[N] = dp[N - 1] + dp[N - 2]의 점화식을 사용하..

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 점화식을 만들기 위해 문제에서 주어진 규칙을 보면, 1. 계단은 한번에 한 계단, 두 계단씩 오를 수 있다. 2. 연속된 3개의 계단을 밟으면 안된다. 이 규칙에서 현재 계단 N을 밟기 위한 방법으로는 N - 2에서 N까지 두 계단 이동한 경우와 N - 3에서 N - 1까지 두 계단 이동하고 N - 1에서 N까지 한 계단 이동한 경우로 2가지만 가능하다. 연속해서 3개의 계단을 밟는 것이 불가능하기 때문에 위의 두 가지 방법이 전부가 된다. 그렇다면 현재 계단에서..

문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 문제는 하나의 자연수를 1, 2, 3으로 조합하여 만드는 경우의 수를 구하는 것으로 우선 1, 2, 3을 만드는 경우의 수를 먼저 확인해보자. 1을 만드는 경우의 수는 (1)으로 1개고, 2를 만드는 경우의 수는 (1 + 1), (2)로 2개, 3을 만드는 경우의 수는 (1 + 1 + 1), (1 + 2), (2 + 1), (3)으로 4개다. 1, 2, 3을 조합하여 4를 만드는 방법은 (1 + 3), (2 + 2), (3 + 1)로 나타낼 수 있는데, (1 + 3)은 (1) + (1 + 1 + 1), (1) + (1 + 2), (1) + (2 + ..

문제 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 파스칼 삼각형을 이용해 점화식을 만들고 이항 계수를 계산해주면 된다. 아래의 이미지는 파스칼 삼각형을 쉽게 이해할 수 있도록 설명해 준다. 파스칼 삼각형은 각 단계의 처음과 끝은 1로 채워주고 그 사이의 항들은 윗 단계에서 더해주는 것으로 계산한다. 이에 대한 수학적 증명은 아래와 같다. $$\displaystyle \binom{n-1}{r-1}+\binom{n-1}{r}=\frac{\left(n-1\right)!}{\left(r-1\right)!\left(n-r\right)!}+\frac{\left(n-1\right)!}..