Problem Solving/백준

[BOJ 백준] 17479번 : 정식당

돌돌김 2020. 9. 10. 02:59

www.acmicpc.net/problem/17479

 

17479번: 정식당

일반메뉴는 noodle 2개로 20,000원, 특별메뉴는 cutlet 2개와 friedrice 1개로 32,000원, 둘이 합쳐 52,000원으로 서비스메뉴 하나를 주문할 수 있다.

www.acmicpc.net

해시 자료구조를 사용하고 싶어서 풀어본 문제

해시 맵을 4개 사용해서 각 메뉴, 가격, 주문수량에 맞게 정보를 저장해주면 된다.

구조체를 사용하여 해시 맵에 저장하면 더 간단하게 풀 수 있는데, 연산자 오버라이딩도 해줘야 해서 그냥 여러개의 해시맵을 만들었다.

 

4번 시도만에 해결했는데 틀린원인은 2개였다

  • service 오타
  • 자료형 범위

오타는 금방 찾았지만, 자료형 범위를 찾는데 좀 오래걸렸다.

각 메뉴등급별로 최대 5만개씩 들어올 수 있고, 각 메뉴당 가격은 100만이다. 

100만원 짜리 메뉴를 5만개씩 기본, 스페셜메뉴에서 전부 주문한다면

50억 + 50억 = 100억이다. (서비스는 가격이 없음)

 

즉, int의 범위를 넘는 것이다.

나는 각 등급별로 주문한 메뉴의 가격의 총합을 int 타입으로 맵에 저장했기 때문에 

처음에는 오버플로우가 났을 것이다.

 

이 부분만 주의하면 어렵지 않은 문제이다.

 

 

 

소스코드는 아래와 같다.

#include<bits/stdc++.h>
#define endl "\n"
#define MAX 10
using namespace std;

map<string, int>menu_price; // 메뉴, 가격
map<string, string>menu_type; // 메뉴, 메뉴 등급(normal, special, serivice)
map<string, int>order_type; // 등급별 주문 수량
map<string, long long>order_price; // 등급별 주문 가격
int a,b,c;
string menu;
int price; 
int n;
int main() {	
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	freopen("input.txt", "r", stdin);
	cin>>a>>b>>c;
    int cnt = a+b+c;
    for(int i=0; i<cnt; i++){
        if(a>0){
            cin>>menu>>price;
            menu_price[menu]=price;
            menu_type[menu]="normal";
            a--;
        }else if(b>0){
            cin>>menu>>price;
            menu_price[menu]=price;
            menu_type[menu]="special";
            b--;
        }else{
            cin>>menu;
            menu_type[menu]="service";
            c--;
        }
    }
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>menu;
        string rank = menu_type[menu]; // 이 메뉴가 어떤 등급인지
        order_type[rank]+=1; // 해당 등급 주문 개수 +1
        if(rank!="service"){
            int pric = menu_price[menu]; // 이 메뉴가 얼마인지
            order_price[rank]+=pric;   // 해당 등급 주문 가격 
        }
    }
/*
특별메뉴는 일반메뉴에서 총 20,000원 이상을 주문해야 주문할 수 있다.
서비스메뉴는 일반메뉴와 특별메뉴에서 총 50,000원 이상을 주문해야 주문할 수 있다.
서비스메뉴는 단 하나만 주문할 수 있다.
*/
    if(order_type["special"]){
        if(order_price["normal"]<20000){ // 일반 메뉴 20,000원 미만 주문 -> 특별 주문 X
            cout<<"No";
            return 0;
        }
    }
    if(order_type["service"]){
        if(order_price["normal"]+order_price["special"]<50000){ // 일반메뉴+특별메뉴 50,000 미만 주문 -> 서비스 주문 X
            cout<<"No";
            return 0;
        }
    }
    if(order_type["service"]>1){
        cout<<"No";
        return 0;
    }
    cout<<"Okay";
   
	return 0;
}