티스토리 뷰

코딩테스트

바닥 공사

ajaa 2024. 10. 31. 21:06

📌문제

가로가 N 세로가 2인 직사각형 형태의 바닥이 있다. 이 얇은 바닥을 1x2, 2x1, 2x2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.

 

📌풀이

1. 왼쪽부터 (i-1)까지의 길이가 덮개로 채워져있다면 2x1의 덮개를 채우는 하나의 경우

2. 왼쪽부터 (i-2)까지의 길이가 덮개로 채워져있다면 1x2 덮개 2개를 넣는 경우

   2x2 덮개 하나를 넣는 경우

 

📌코드

n = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001

# 다이나믹 프로그래밍(보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
    d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796

print(d[n])

 

 

📌참고

https://g.co/kgs/eyd5SSd

 

이것이 취업을 위한 코딩 테스트다 with 파이썬

IT 취준생이라면 누구나 입사하고 싶은 카카오・삼성전자・네이버・라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다! IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년

www.google.com

 

 

'코딩테스트' 카테고리의 다른 글

최단 경로  (0) 2024.11.03
효율적인 화폐 구성  (1) 2024.11.01
개미 전사  (2) 2024.10.30
1로 만들기  (0) 2024.10.29
다이내믹 프로그래밍  (5) 2024.10.28
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함