oiehso0

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

풀이

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

풀이

문제 설명이 구체적으로 되어있지 않아서 헤맸다.

ex)

arr[1][1]    arr[1][2]    arr[1][3]    arr[1][4]

arr[2][1]    arr[2][2]    arr[2][3]    arr[2][4]

arr[3][1]    arr[3][2]    arr[3][3]    arr[3][4]        와 같은 2차원 배열이 존재한다고 하고

문제를 이해하기로는 

i,j,x,y에 2,2,3,3을 주면

arr[1][1]    arr[1][2]    arr[1][3]    arr[1][4]

arr[2][1]    arr[2][2]    arr[2][3]    arr[2][4]

arr[3][1]    arr[3][2]    arr[3][3]    arr[3][4]    <-- 빨간 부분의 배열의 총 합을 구하는 거라고 생각했지만 X

arr[1][1]    arr[1][2]    arr[1][3]    arr[1][4]

arr[2][1]    arr[2][2]    arr[2][3]    arr[2][4]

arr[3][1]    arr[3][2]    arr[3][3]    arr[3][4]   <-- 이와 같이 사각형의 형태의 배열의 총 합을 구하는 문제였다.

그래서 나는 dp[i][j]를 이용해서 arr[1][1] 부터 arr[i][j]까지  총합을 구했다.

for (int i = 1; i <= N; i++) {

dp[i][1] = arr[i][1] + dp[i - 1][M];

for (int j = 2; j <= M; j++) {

dp[i][j] += dp[i][j-1] + arr[i][j];

}

}

그후에  x좌표의 값을 기준으로 for문을 이용해 이전에 구해 놓았던 dp값을 활용해서 한줄씩 부분 배열의 합을 구하기로 한다.

for (int i = 1; i <= T; i++) {

scanf("%d %d %d %d", &a, &b, &x, &y);

for (a; a <= x; a++) {

r += dp[a][y] - dp[a][b]+ arr[a][b];

}

printf("%d\n", r);

r = 0;

}

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

풀이

파도반 수열은 피보나치 수열과 어느정도 닮은 부분이 있는데 삼각형을 나선으로 계속 추가하는데 가장 긴 변에 삼각형을 계속 추가한다. 이러한 특성 때문에 처음에

긴변이 생기기 전까지 변의 길이는 p(1)    =    p(2)    =    p(3)    =    1 로 동일하다.

초기 값을 제외하고 이후의 값들의 규칙을 찾아보면 

p[i]    =    p[i-1] + p[i-5]; 와 같은 형태를 띄는 것을 차례대로 삼각형을 추가하며 그려보면 어렵지 않게 알 수 있다.

또는 p[i]    =    p[n-2] + p[n-3];과 같은 규칙도 띈다.