boj 10836 : 여왕벌

boj 10836 : 여왕벌

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

시간을 오래 들여 여러 실험을 해본 문제이다.

주어지는 n개의 m*2-1배열이 감소하지 않는 것에 문제의 힌트가 있다.

따라서 문제는 m*2-1배열을 읽었을 때 0,1,2만큼 자라는 수가 주어지고, 이를 통해 왼쪽모서리와 위쪽모서리의 애벌레들이 최종적으로 얼마나 자랐는지를 구해낼 수 있다.

왼쪽,위쪽 모서리의 에벌레들만 자라고 나면 나머지 에벌레들은 각 열의 맨 윗쪽 모서리 애벌레 크기만큼 자란다. 왜냐하면 주어지는 배열이 감소하지않는 배열이기 때문!

그렇다면 문제는 모서리 왼쪽위쪽 애벌레가 모두자랐을 때 크기가 얼마나 되느냐?만 풀면 된다.

총 3가지 방법으로 시도해보았다.

1. 애벌레 크기 다 계산하기.

총 2m-1 마리의 애벌레들의 크기 배열을 만들어 n번 loop를 돌며 2m-1번 각각 애벌레가 자라는 수치를 더해준다.

이렇게되면 시간복잡도는 m*n으로 약간 애매하다. (시간초과 날 때도 있었고 잘 짜면 시간초과 안나기도 함)

2.펜윅트리

https://www.acmicpc.net/blog/view/21(설명이 잘 되어 있다.)

구간트리의 방법으로 구하였다.

구간트리는 k번째 숫자를 임의의 수 만큼 더하는 과정을 n번 반복했을 때 의 구간합을 구하는 것을 빠르게 해주는 자료구조이지만(시간복잡도 : nlogk), 이를 약간 변형하면 일정범위에 임의의수를 n번 더하는 과정을 반복했을 때 특정수의 값을 구하는 자료구조로 변형시킬 수 있다.

3. 범위구간합 응용

간단한걸 생각못해서 펜윅트리를 이용했다 ㅜㅜ 이방법이 제일 떠올리기 쉬운데, 각각 1만큼 자라는 애벌레의 시작지점, 2만큼 자라는 애벌레의 시작지점을 누적하여 최종적으로 애벌레가 얼마나 자랐는지 알 수 있다.

while (n--) {

scanf("%d%d%d", &t1, &t2, &t3);

a[t1]++;

a[t1+t2]++;

/*t1,t2,t3,가 각각 0,1,2만큼 자라는 애벌레이기때문에 t1은 1만큼 자라는 애벌레의 시작점, t1+t2는 2만큼 자라는 애벌레의 시작점이다.*/

}

for (int i = 1; i < 2 * m - 1; i++) a[i] += a[i - 1];

//위의 for문과 같이 해주면 최종적으로 애벌레가 얼만큼 자랐는지를 구할 수 있다.

2,3의 방법을 해주었을때 2의 방법의 시간복잡도는 nlogm, 3의 방법의 시간복잡도는 n인데 신기하게도 3번의 방법이 더 느리다.. 왜일까