[PART2] 8-3(DP): 바닥 공사 ❗
💥이코테 실전문제 뽀개기💥
💻 8-3 바닥 공사
난이도🖤🖤🖤🤍🤍🤍 | 풀이시간 20분 | 제한시간 1초 | 메모리제한 128MB
📌2021/02/01 작성 코드
n = int(input())
dptable = [0]*1001
dptable[1] = 1
dptable[2] = 3
for i in range(1, n+1):
if dptable[i] != 0:
continue
dptable[i] = (dptable[i-1] + dptable[i-2]*2)%796796
print(dptable[n])
💭 아이디어
-
솔루션이 쉽게 떠오르지 않아서 해설을 먼저 참고하고 혼자 코드를 짰다.
-
혼자 정리해 본 아이디어는 이렇다.
🔴 백준 11727 문제와 유사하다
https://velog.io/@eastgloss0330/%EB%B0%B1%EC%A4%80-11727-2n-%ED%83%80%EC%9D%BC%EB%A7%81-2Python
🤓 문제 해설
결과값이 굉장히 커질 수 있기 때문에 값을 계산할 때마다 796796으로 나눈 나머지만 취하도록 한다.
왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있다.
- 왼쪽부터 i-1까지 길이가 덮개로 이미 채워져 있으면 2x1의 덮개를 채우는 하나의 경우밖에 존재하지 않는다.
- 왼쪽부터 i-2까지 길이가 덮개로 이미 채워져 있으면 1x2 덮개 2개를 넣는 경우, 혹은 2x2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다.
이 문제 역시 왼쪽부터 N-2 미만의 길이에 대해서는 고려할 필요가 없다. 왜냐하면 사용할 수 있는 덮개의 형태가 최대 2x2의 직사각형 형태이기 때문이다.
ai = ai-1 + a i-2x2🤓 답안 예시
# 정수 N을 입력 받기
n = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001
# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
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])
🤔 리뷰
- 타일링 관련 문제들 풀어보면서 복습하자
Author And Source
이 문제에 관하여([PART2] 8-3(DP): 바닥 공사 ❗), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@eastgloss0330/PART2-8-3DP-바닥-공사저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)