다이나믹

[python] 백준 - 2133. 타일 채우기

🤔문제 해결 S2 | DP 이런문제는 역시 단골 DP문제 일단 손으로 구해봤다. i == 0, 2, 4, 6 ( 홀수 일 경우는 제외함 ) 경우의수 == 1, 3, 11, 41 점화식 dp[i] = dp[i-2] * 3 + (dp[2] ~ dp[i-2]) * 2 + 2 i경우의수 = 이전의 경우의 수 * 3 + 이전의 경우의 수 들 * 2 + i만 만드는 경우 💻소스 코드 N = int(input()) if N % 2: print(0) else: dp = [0] * (N + 1) dp[0], dp[2] = 1, 3 for i in range(4, N + 1, 2): dp[i] = dp[i - 2] * 3 + 2 for j in range(2, i - 2, 2): dp[i] += dp[j] * 2 prin..

[python] 백준 - 1309. 동물원

🤔문제 해결 1. S1 | DP 2. 사자가 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 오른쪽에 있는 경우의 리스트를 만든다. 3. i번째에서 i-1번째에 사자의 상태에 따라 i번째의 경우의 수가 결정된다. (1) i번째에 사자가 없는 경우는 i-1번째에 사자가 왼쪽, 오른쪽 그리고 없어도 된다. (2) i번째에 사자가 왼쪽에 있는 경우는 i-1번째에 사자가 오른쪽에 있는 경우와 없는 경우만 가능하다. (i-1번째에 왼쪽에 있으면 i번째에서는 왼쪽에 있을 수 없다) (3) 오른쪽도 마찬가지 4. 경우의 수를 점차 더해나가면서 마지막 경우의 수를 다 더해준다. 💨 마지막에만 9901로 나누려고하면 메모리초과가 발생한다. 값을 쌓을 때 부터 나눠주면서 하자. 💻소스 코드 if __name__ == "__..

[python] 백준 - 1495. 기타리스트

🤔문제 해결 1. S1 | 다이나믹프로그래밍 2. 각각의 연주 차례에 가능한 볼륨을 저장하기 위해 2차원 리스트를 만든다. 3. 리스트를 설명하자면 맨 첫줄(i = 0)은 연주 시작전 단계이고 값이 0이 아니라 1인 부분은 내가 가지고 있는 볼륨이다. 현재 테스트케이스 예시(S=5)로 작성됐으므로 [0][5] = 1 이다. 4. 테스트케이스: 시작값 5, 최대값 10, 연주리스트 = [5, 3, 7] 5. 첫번째 연주를 하기 전에 볼륨을 바꾼다. 현재 볼륨은 5, 첫번째 연주 볼륨은 5 이므로 5+5 = 10, 5-5 = 0 으로 둘다 0보다 크고 10보다 작으므로 아래와 같이 저장할 수 있다. 6. 첫번째 연주를 하기 전에 볼륨을 바꾼다. 첫번째와 다른점은 현재 볼륨이 2가지(0과 10)이다. 먼저 현..