🧚‍♂️알고리즘🧚‍♂️ - 동적 계획법(DP) 2

실버 3

2193

2193번: 이친수

 - 0으로 끝나는 이친수의 개수와 1로 끝나는 미친수의 개수를 카운팅하는 배열을 만들어서 DP ㄲㄱ ㄱ

 

1은 0을 낳

0은 1과 0을 낳

 

0은 이전 0,1 합

1은 이전 0 개수

from sys import stdin
N = int(stdin.readline()) # N자리

Nlist = [[0,1]]

for i in range(N-1):
    zero = Nlist[-1][0]
    one =  Nlist[-1][1]
    nlist = [zero + one,zero]
    Nlist.append(nlist)

print(sum(Nlist[-1]))

---

실버 3

11726

11726번: 2×n 타일링

이거 이퍼 기출이자나~

---

실버 1

10844

10844번: 쉬운 계단 수

자릿수가 하나 늘어날 때마다 2개씩 더 생김 (앞 숫자가 고정되어있을 때)

 

처음에 오는 수 1-9 (9개)

다음에 오는 수 각각 2개씩 (9*2)

다다음에 오는 수 거기에 각각. 2개씩 (9*2*2)

근데 이러면 범위 벗어나는 ㄱ서 보기 힘들구나 0이랑 9 넘어가면

 

=> 각 자릿수마다 끝 자리숫자 0-9 각각 저장하기

0이랑 9는 1랑 8을 한개씩

나머지는 앞뒤를 한개씩

 

0은 이전 1를 그대로

9는 이전 8을 그대로

나머지는 이전 전수,후수의 합

0고려어ㅏ악

from sys import stdin
N = int(stdin.readline()) # N자리

Nlist = [[0 for _ in range(10)] for _ in range(N+1)]

for i in range(1,10):
    Nlist[1][i] = 1 #초기 설정

for i in range(2,N+1): #길이 i
    Nlist[i][0] = Nlist[i-1][1]
    Nlist[i][9] = Nlist[i-1][8]
    for j in range(1,9): 
        Nlist[i][j] = (Nlist[i-1][j-1] + Nlist[i-1][j+1]) #여기도 미리 나눠주면조음!

print(sum(Nlist[N])%1000000000)

으아악 졸려

오늘 학교수업을 복습하고..잔다