buzz

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 해설 방법의 수를 계산해보면 1, 2, 4, 7, 13, 24가 나오는데 이걸 보면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]인 것을 알 수 있다. 처음엔 5까지만 방법의 수를 세보고 dp[i]의 방법의 수는 그 이전 수들의 방법의 수의 총합이라고 생각했는데 6까지 세어보니 완전 아니었다.. 완전 헛짓거리 하고 있었다. 코드 -파이썬 #백준 9095(1, 2, 3 더하기) t = int(input()) dp = [0] * 11 dp[1] = 1 dp[2] = 2 dp[..

문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 해설 이 문제는 dp문제로 규칙만 찾으면 쉽게 풀 수 있다. 처음엔 2*5까지 직접 정리해보고 dp[i] = dp[i-1] + dp[i-2] + (2*(i-2)-1) 인 줄 알았다. 그러나 백준 예제입력2만 해봐도 이게 아니란 걸 알 수 있다. 규칙 찾는데 약간 헤맸지만 자세히 보면 dp[i] = dp[i-1] + (dp[i-2]*2)규칙을 찾을 수 있다. dp[i-1]과 dp[i-2]를 알아내려면 최소한 dp[1], d..

문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 해설 이 문제는 dp 문제이다. 위 그림을 보면 n = (n-1) + (n-2) 임을 알 수 있다. 결국 dp[1]과 dp[2]의 개수만 미리 넣어놓는다면 그 후 dp[n]의 개수들은 쉽게 구할 수 있다. 다만, dp 배열을 초기화할 때 dp = [0] * (1001)이 아니라 dp = [0] * (n + 1)을 해주면 런타임 에러가 뜨는데 왜 뜨는지 모르겠다.. 코드 -파이썬 #백준 11726(2*n 타일링) ..