목록2023/12/10 (1)

잡다한 IT 지식

1309번: 동물원(Kotlin, C++)

제한사항 1 ≤ N ≤ 100,000 첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라. 문제 정리 사자는 자신의 주위(사방면)에 다른 사자가 있으면 안된다. 사자를 둘 수 있는 방법을 모두 구하시오. 접근 방법 DP라고는 생각했는데 제한 시간 내에 못 풀어서 다른 사람 답안 봤습니다. 핵심은 위에 사자가 있는 경우와 위에 왼쪽에 사자가 있는 경우 위에 오른쪽에 사자가 있는 경우를 생각해서 풉니다. case1) 현재 블록에 사자를 안 두는 경우 이 경우에는 위에 사자가 어디 있든 지 상관 없습니다. 따라서, 아래 세 가지 수의 합이 사자를 안 두는 경우입니다. 위에 사자가 없는 경우(dp[n-1][0]) 위에 왼쪽에 사자가 있는 경우(dp[n-1][1]) 위에 오른쪽에 사자가 있..
알고리즘 문제 풀이 2023. 12. 10. 21:26
이전 Prev 1 Next 다음