[백준] 2560 짚신벌레

2560번: 짚신벌레

문제 확인

 

원형 큐 자료구조 형식을 응용하는 문제입니다.

모든 짚신벌레를 관리하면 메모리 초과가 일어나며 a, b, d를 고정시키고 배열을 움직이게 되면 연산이 많아져 시간 초과가 납니다. 따라서 배열의 값 대신 a, b, d를 인덱스로 이용하여 풀어야 합니다.

 

풀이

 

문제에서 주어진 d 값을 이용해 원형 큐 배열을 만듭니다. d는 최대 10000이며 이를 넘을 시 짚신벌레는 죽기 때문에 배열을 ary[10001]로 선언합니다.

초기 배열을 [1, 0, 0, ...] 으로 초기화해주고 a, b, d를 인덱스로 활용해야 하기 때문에 처음과 끝을 알려주는 값 front, end 값을 설정해둡니다. front의 의미는 성체가 새 게체를 만들어내는 위치를 의미하며 d 다음에 오는 위치, 즉 0이 됩니다. end는 원형 큐에서 인덱스들이 움직이다가 0 다음에 올 위치를 의미하며 초기 d 값과 같습니다.

인덱스 a, b, d, front 들은 원형 큐에서 움직이므로 다음 위치는 idx = idx!=0 ? : idx - 1 : end 가 됩니다.

a~b 사이에 있는 성체의 수는 초기 0마리이며 투포인터 알고리즘을 이용해 a~b를 모두 탐색하지 않고 구할 수 있습니다. adult = adult + ary[a] - ary[b] 가 됩니다.

이를 통하여 문제를 풀어봅니다.

 

백준에 예시 2 4 6 6 을 통해 설명하겠습니다.

 

초기 상태

초기 상태는 다음과 같습니다. 인덱스 a, b, d, front는 각 배열의 인덱스를 가리키고 end는 초기 d 값인 6으로 고정입니다.

 

n=1

n = 1 : a, b, d, front가 원형 큐를 따라 한칸 앞으로 움직이게 되고 의미를 생각해보면 배열 0에는 1년 지난 짚신벌레, 1에는 2년 지난 짚신벌레의 수가 담겨 있다고 볼 수 있습니다.

 

n = 2

n = 2 : 성체의 수가 1이 되어 새 게체 1마리를 만들게 되고 이는 front에 저장이 됩니다.

 

n = 3, 4, 5

같은 과정을 진행합니다. n = 5인 날에는 adult 값이 2가 되어 front에는 2마리의 새 게체가 생성됩니다.

 

n = 6

n = 6 : 이날에 ary[d]에 짚신벌레가 있으므로 이들은 죽게 되어 0이 됩니다. 따라서 결과는 2 + 2 + 1 + 1 + 1 = 7이 됩니다.

 

한 가지 주의해야 할 점은 adult를 계산 시 long long 값을 벗어나서 잘못된 값이 기록될 수 있습니다. 이를 방지하기 위해 음수 값이 잘못 저장되지 않도록 adult = (adult + ary[a] - ary[b] + 1000) % 1000으로 기록을 합니다.

 

코드

#include <cstdio>
int main() {
    int ary[10001] = { 1 }, adult = 0;
    int a, b, d, n, front = 0, end;
    scanf("%d%d%d%d", &a, &b, &d, &n);
    if (a > n) {
        printf("1");
        return 0;
    }
    end = d;
    while (n--) {
        a = a != 0 ? a - 1 : end;
        b = b != 0 ? b - 1 : end;
        d = d != 0 ? d - 1 : end;
        front = front != 0 ? front - 1 : end;
        adult = (adult + ary[a] - ary[b] + 1000) % 1000;
        ary[front] = adult;
        ary[d] = 0;
    }
    a = 0;
    for (int i = 0; i <= end; i++)
        a += ary[i];
    printf("%d", a % 1000);
}