다이나믹프로그래밍
백준 2579: 계단오르기 해설- python
✏️ 문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ✏️ 풀이 케이스는 두가지로 분리된다. 이전에 두 계단을 연속으로 오른 경우. 그리고 3계단 이전에는 두계단을 오르고 바로 이전에서 현지점까지 연속으로 올라오는 경우. 본 문제에서는 리스트를 두개 만들었다. i번째 계단까지 최대값을 저장하는 dp[] & 문제에서 준 계단점수를 저장하는 arr[] 이를 점화식으로 나타내보면 아래와 같을 것이다. 1. dp[i-2] + arr[i] 2. dp[i-3] + arr[i-1] + arr[i] n=int(input()) ar..
백준 11726: 2xn 타일링 해설- python
✏️ 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ✏️ 풀이 뭘 어쩔지 모를땐 늘 그렇듯 규칙을 찾아보자. 모든 경우의 수를 한번 생각해보았다. n=1 > size 1 : 1개 n=2 > size 1: 2개 || size 2: 1개 n=3 > size 1: 3개 || size 1: 1개 + size 2: 2개 || size 1: 2개 + size 2: 1개 n=4 > size 1: 4개 || size 1: 2개 + size 2: 2개(L) || size 1: 2개 + size 2: 2개(R) || size 1: 1개 + s..