골랜디 #10 3078번

Published at: 2025-03-29

Last modified at: 2025-03-29

오늘 푼 문제

안녕하세요 한라나입니다.
오늘은 정말 오랫만에 방송을 킨 날이었어요.
엘든링이 할인을 하길래 한번 해볼까 했죠.
…이렇게 거지같은 게임은 난생 처음 해봅니다.

오늘의 문제는 아래와 같습니다.

처음에 자료구조 + 큐 + 슬라이딩 윈도우라고 하길래 잉??? 했습니다.
근데 훼이크였어요, 전 슬라이딩 윈도우 하나 써서 풀었습니다.
물론 정해는 큐를 썼겠죠. 근데 전 그렇게 안 했어요.
라고 쓰고 나서 생각해보니까, 큐를 써도 되겠네요. 근데 메모리 제한이 안 빡세서 굳이 라는 느낌입니다.
라기 보단, 어차피 N=300000, K=N이면 메모리가 그냥 제 코드랑 똑같을텐데, 그러면 진짜 굳이??

암튼 풀이는, 슬라이딩 윈도우가 주력입니다.
그런데 누적으로 합 하는게 하나의 수가 아니고, 이름의 길이 별로 다르게 하는거에요.
그러니까 앞에 K칸에 이름이 2글자인 애는 몇명… 3글자인 애는 몇명…을 저장해 두고, 한칸한칸 옮겨갈 때마다 K 범위를 벗어나는 사람의 이름 갯수에 해당하는 수를 하나 지우고, 옮겨온 사람의 이름의 갯수에 해당하는 수를 하나 넣어줍니다.
그리고 본인 이름 수에 해당하는 ‘몇 명’을 답에 계속 더해주면 됩니다.
다만 아직 K등까지 오지 않았다면 뺄 사람이 없으니까 그건 잘 보고 해주어야 합니다.

for(i=1;i<n;i++) {
    scanf("%s", name);
    numbers[i] = strlen(name);
    ans += nameLength[numbers[i]];
    nameLength[numbers[i]]++;
    if(i>=k) nameLength[numbers[i-k]]--;
}

근데 ans를 long long int로 하지 않으면 오버플로우가 나요! 주의하세요.

하… 엘든링을 하면서 세상의 부조리함을 배웁니다.

감사합니다.

+10은 1로 시작해서 1과 2 사이에 올라가네요… 이제부턴 순서 지정도 해줘야 하나 봅니다.

---

전체 코드

#include <stdio.h>
#include <string.h>

//using namespace std;

int numbers[300010] = {0, };
long long int nameLength[21] = {0, };

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int i;
    char name[25];
    scanf("%s", name);
    numbers[0] = strlen(name);
    nameLength[numbers[0]]++;
    long long int ans = 0;
    for(i=1;i<n;i++) {
        scanf("%s", name);
        numbers[i] = strlen(name);
        ans += nameLength[numbers[i]];
        nameLength[numbers[i]]++;
        if(i>=k) nameLength[numbers[i-k]]--;
    }
    printf("%lld", ans);
    return 0;
}