일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- linux
- 정보보안기사
- 정보보안
- 레디스
- 다이나믹프로그래밍
- LangChain
- java
- 코딩테스트
- 백준
- springboot
- 파이썬
- 카카오페이
- FastAPI
- t검정
- t-test
- Python
- 리눅스
- 우선순위큐
- 자료구조
- 그리디
- 데이터사이언스
- lightsail
- 시간초과
- 카카오페이면접후기
- 보안기사
- 보안
- synflooding
- 프로그래머스
- 분산시스템
- 딥러닝
Archives
Techbrad
[백준] 1309번 동물원 DP - 파이썬 본문
반응형
https://www.acmicpc.net/problem/1309
풀면서 어려웠던 점
1. DP 테이블을 만들면서 사자를 한마리도 배치하지 않는 경우를 생각해내기 힘들었다.
2. 메모리 초과
DP 테이블에서 한마리도 배치않는 경우 0, 1에 배치할 경우 1, 2에 배치할 경우 2로 정한 후에 풀게되면 수월하게 풀 수 있었다.
그리고 int 형은 4Byte라 문제가 없어보이는데 왜 메모리 초과가 발생하는지에 대해 의문이다. 혹시라도 지나가다가 명확히 아시는 분이 있으면 댓글을 부탁드립니다. ㅜ.ㅜ
N이 100,000이 최대이니까 300,000 개의 int가 있고 이는 1,200,000 byte이고 1.2M 정도 밖에 안되지만 무슨 이유일까... 아무튼 dp를 계산해줄 때 9901을 나눈 나머지를 사용하면 된다.
최종 제출 코드
N = int(input())
dp = [[0, 0, 0] for _ in range(N)]
dp[0][0], dp[0][1], dp[0][2] = 1, 1, 1
for i in range(1, N):
dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901
print(sum(dp[N-1]) % 9901)
반응형
'Programming > 코딩테스트' 카테고리의 다른 글
[백준] 1406번 에디터 - 파이썬 (0) | 2024.05.24 |
---|---|
[Python] sort 정렬 순서 (0) | 2024.05.21 |
코테 후기 - 시간 복잡도 (0) | 2024.04.03 |
[백준] 1966번 프린터 큐 - 파이썬 (1) | 2024.02.18 |
[프로그래머스] 할인 행사 - 파이썬 (2) | 2024.02.04 |