[BOJ] 1309번: 동물원

https://www.acmicpc.net/problem/1309


D[i]를 2*i 크기의 동물원에 사자를 배치하는 경우의 수라고 할 때,


최초로 사자가 들어있지 않은 행이 0행인 경우 : D[i-1]


최초로 사자가 들어있지 않은 행이 1행인 경우 : 2*D[i-2]


최초로 사자가 들어있지 않은 행이 2행인 경우 : 2*D[i-3]


.


.


최초로 사자가 들어있지 않은 행이 i행인 경우 : 2*D[0]


모든 행에 사자가 들어있는 경우 : 2


이므로 D[i] = D[i - 1] + 2 * (D[i-2]+D[i-3]+...+D[0]) + 2가 됩니다. 이 때 D[0]~D[j]까지의 합을 저장하고 매번 구할 때 마다 D[i-1]을 추가하는 식으로 진행하면 O(n)만에 계산할 수 있습니다.(그렇지 않을 경우 O(n^2)이 되어 시간 초과가 발생할 것입니다.)


https://github.com/encrypted-def/BOJ/blob/master/1309.cpp



'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 11653번: 소인수분해  (0) 2018.01.03
[BOJ] 10815번: 숫자 카드  (0) 2018.01.03
[BOJ] 1699번: 제곱수의 합  (0) 2018.01.03
[BOJ] 10162번: 전자레인지  (0) 2018.01.01
[BOJ] 1182번: 부분집합의 합  (0) 2018.01.01
[BOJ] 11403번: 경로 찾기  (0) 2018.01.01
  Comments