[알고스팟] 회전초밥

문제 링크

회전초밥

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • SUSHI
  • 8000ms
  • 65536kb
  • 1899
  • 628 (33%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

문제 풀이 내기에서 모인 벌금이 많이 쌓여서 알고스팟 운영진들은 회식을 하러 회전초밥집에 갔습니다. 회전초밥집에 들어선 운영진들은 초밥은 먹지 않고 전략 회의를 시작했습니다. 회전초밥집에는 n종류의 메뉴가 있는데, 운영진들은 각 메뉴에 대해 선호도를 매겼습니다.

초밥	계란	연어	장어	대뱃살	스테이크	후라이드 치킨
가격	2500	3000	4000	5000	10000	15000
선호도	7	9	10	12	20	1

운영진들은 주어진 예산 안에서 선호도의 합을 최대한으로 하도록 초밥을 먹고 싶습니다. 각 종류의 초밥은 무한정으로 공급된다고 가정합시다. 이 때 얻을 수 있는 최대한의 선호도는 얼마일까요?

입력

입력의 첫 줄에는 테스트 케이스의 수 c(1 <= c <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 초밥의 종류 n(1 <= n <= 20)과 운영진들의 예산 m (1 <= m <= 2,147,483,647)이 주어집니다. 그 후 n 줄에 각 초밥의 가격과 선호도가 순서대로 주어집니다. 가격은 20,000 이하의 자연수로, 항상 100 의 배수입니다. 선호도는 20 이하의 자연수입니다.

출력

각 테스트 케이스별로 한 줄에 가능한 선호도의 최대 합을 출력합니다.

예제 입력

2
6 10000
2500 7
3000 9
4000 10
5000 12
10000 20
15000 1
6 543975612
2500 7
3000 9
4000 10
5000 12
10000 20
15000 1 

예제 출력

28
1631925

어떻게 풀까??

예전에 이런 비슷한 문제를 푼 적이 있었습니다!

해당 문제에서 핵심은, 0 원부터 보면서 최대 선호도가 얼마나 되는지를 확인해 보는 것이죠!

우선, 최대 선호도는 어떻게 결정되는지 봐야합니다!

자 위와 같이 가격이 M인 곳에서 시작한다고 합시다!

물건이 3 개라면, M인 곳의 최대 선호도는 각각의 물건가격을 뺀 가격 에서의 최대 선호도들에 물건의 선호도를 더한 것들 중에서 최대인 것을 선택하면 될 것입니다!

위의 경우에서, 가격이 M인 곳의 최대 선호도는

가격이 M-4000일 때의 최대 선호도 + 1,

가격이 M-3500일 때의 최대 선호도 + 9,

가격이 M-2500일 때의 최대 선호도 + 7 중 가장 큰 값이 되겠죠!

이제 이 가격을 0일 때부터 차근차근 계산하면, 항상 최고의 값을 가지는 선호도들을 선택할 수 있을 것입니다!! 

이렇게 되면 점화식은 다음과 같이 쓸 수 있을 것입니다!

그런데, 이 문제를 그대로 풀려고 하다간 

첫번째로, 10^9이 되는 속도에 절망하고 말겁니다. 결국 0원부터 시작해서 운영진들의 예산까지 선형으로 해결해야 하기 때문이죠!

10^8을 1초로 생각한다면, 10초가 걸린다는 말이되죠!

하지만, 문제에서 핵심은 가격이 100원 단위라는 것이죠! 이를 이용해서, 운영진들의 예산을 100으로 나누면,

10^7이 되버립니다!!! 반복문도 굉장히 간단하게 나타나기 때문에 빠른 시간 내에 문제를 풀 수 있습니다.

두번째로, 메모리의 문제입니다!

10^7이라 해도, sizeof(int) * 2* 10^7이 약 80MB정도 되므로 해당 문제 메모리 제한에 걸려버리게 됩니다.

하지만, 문제의 가격이 2 만원을 넘지 않는다는 것에 주목해야 합니다! 다른 말로하면, 현재 가격에서 2만원 이전의 값은 보지도 않는다는 것이죠! 쓸모없는 메모리인 것입니다.

여기서 이용해야하는 것이 바로 슬라이딩 윈도우 테크닉입니다!

어짜피 2만원 이전의 가격은 보지 않는다면, 메모리를 201개만 만들어서 나머지 연산자를 통해 이전 값들의 위치에 현재 값을 씌우는 것입니다!

59800에서 2만원 물건 가격의 선호도를 계산하는 경우의 인덱스를 살펴봅시다!

59800 % 20001 = 19798이고, 39800%20001 = 19799 입니다.

그리고 다음 59801 % 20001 = 19799이고, 여기서 최대 선호도를 확인할 때에는,

어짜피 물건의 가격이 2 만원까지밖에 되지 않기 때문에, 39800의 물건 값에대한 정보는 필요가 없는 것이죠!

따라서, 19799 인덱스에 있는 정보에 덮어써도 되는 것 입니다!

(예에서는 좀 더 원활한 확인을 위해서 20001개의 배열을 만들었지만, 실제로는 201개의 배열만 만들면 됩니다!)

이렇게 메모리 공간도 줄였다면, 이제 문제를 풀 수 있을 것입니다!

코드

#pragma once
#include<cstring>
#include<cstdio>
int cache[201];
int prices[20], money;
int favor[20];
 
int max(int i1, int i2) {
    return i1 > i2 ? i1 : i2;
}
 
int main() {
    int t;
    scanf("%d\n", &t);
 
    while (t--) {
        int n;
 
        scanf("%d %d\n", &n, &money);
        money /= 100;
 
        for (int i = 0; i < n; i++) {
            scanf("%d %d\n", &prices[i], &favor[i]);
            prices[i] /= 100;
        }
        memset(cache, 0, sizeof(cache));
 
        for (int i = 0; i < money; i++) {
            for (int j = 0; j < n; j++) {
                int nni = (i + prices[j]) % 201;
                int ni = i % 201;
                //슬라이딩 윈도우
                cache[nni] = max(cache[ni] + favor[j] , cache[nni]);
            }
        }
 
        printf("%d\n", cache[money % 201]);
    }
    return 0;
}

여담

시간 복잡도는 가격에 비례 합니다!

가격이 n이라고 한다면, 시간복잡도는 O(n) 이죠!