-
1904. [Python]01타일Python_알고리즘/Silver III 2023. 6. 5. 22:59
1. 문제
https://www.acmicpc.net/problem/1904
2. 접근 방법
- 시간 제한: 0.75초
- 메모리 제한: 256MB
- DP(다이나믹 프로그래밍)
3. 파이썬 코드
N = int(input()) dp = [1, 2] for i in range(2,N): dp.append((dp[i-2]+dp[i-1])%15746) print(dp[N-1])
4. 문제를 풀고난 후 생각
- 문제를 읽어본 후 직접 타일의 갯수에 따른 변화를 생각해보며 코드 구현을 생각했다.
ex)
1개 일 경우 => 1 1개
2개 일 경우 => 11 00 2개
3개 일 경우 => 100 001 111 3개
4개 일 경우 => 1100 1001 0011 1111 0000 5개
5개 일 경우 => 11100 11001 10011 00111 10000 00100 00001 11111 8개
6개 일 경우 => 111100 111001 110011 100111 001111 110000 100100 001100 001001 100001 000011 000000 111111 13개
...
- 위와 같은 식으로 증가하는데 이 증가되는 갯수를 보며 피보나치 수열로 증가한다는 것을 알게 되었고 이에 따른 코드를 작성하였다.
- 여기서 나온 조건으로는 메모리 초과를 방지하기 위해서 15746으로 나눈 나머지를 구해야기 때문에 연산을 진행하면서 나눠준 값을 넣어줬다.
5. 문제를 푸는데 도움이 되는 지식
- 다이나믹 프로그래밍
'Python_알고리즘 > Silver III' 카테고리의 다른 글
2371. [Python]파일 구별하기 (1) 2023.06.11 1448. [Python]삼각형 만들기 (1) 2023.06.06 2312. [Python]수 복원하기 (8) 2023.06.04 1270. [Python]전쟁 - 땅따먹기 (0) 2023.05.30 2149. [Python]암호 해독 (0) 2023.05.30