๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ
-
[BaekJoon] 11659๋ฒ : ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ 4SW Test/BaekJoon 2021. 4. 19. 21:29
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด Prefix sum ๊ตฌํ๊ธฐ ๋ฌธ์ ์ ๋๋ค. DP๋ฅผ ์ฌ์ฉํ๋ฉด ์๊ฐ๋ณต์ก๋ O(N)์ ๊ตฌํ ์ ์์ต๋๋ค. D[i] = D[i-1] + D[i-2] +... +D[1] #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int arr[100000]={0}; int n,m; cin>>n>>m; for(int i=1;i>arr[i]; arr[i]+=arr[i-1]; } for(int i=0;i>a>>b; cout