- [H1730] 미식왕! 기문!
※ 문제 및 풀이에 대해 사외 온라인/오프라인에 게시/공유 하는 것은 금지되어 있습니다.
SW Expert 아카데미의 문제는 삼성전자 직원에게만 오픈 되어 있습니다.[제한 사항]
시간
12개 테스트케이스를 합쳐서 C/C++의 경우 1초 / Java의 경우 2초 / Python의 경우 2초
메모리
힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내
미식가 중 왕인 미식왕은 2가지 능력을 갖춰야 한다.
맛을 이해하는 능력! 그리고 언제든 평가하기 위해 많이 먹을 수 있는 능력!
모든 미식왕은 2가지 능력을 수치로 표현할 수 있다!
양천주가 출신 기문이는 이제 갓 미식왕 협회에서 활동하기 시작했다. 이제 막 시작했기 때문에 이해력, 소화력 모두 1 밖에 되지 않는다.
이제 기문이는 세계 맛집 투어를 다니며, 미식왕로서의 능력을 키울 것이다.
맛집은 모두 총 N개가 있으며, 각 맛집 마다 타이틀 음식이 존재한다.
타이틀 음식을 섭취하기 위해서는 최소한의 이해력이 필요하거나, 서빙되는 음식 양을 모두 소화할 수 있어야 한다.
즉, 미식왕의 이해력이 음식의 이해력보다 이상이거나, 소화력이 음식의 양보다 이상이어야 한다.
기문이는 특성 상 타이틀 음식을 섭취하면 미식왕 능력을 올릴 수 있는 점수를 받을 수 있으며, 해당 점수를 이해력 혹은 소화력에 자기 마음대로 분배할 수 있다.
예를 들어, 이해력 8, 소화력 5인 사람이 음식을 먹어서 4의 점수를 받으면 (이해력, 소화력)이 (8, 9), (9, 8), (10, 7), (11, 6), (12, 5) 중 하나로 변할 수 있는 것이다.
기문이는 맛집 투어를 자기가 원하는 순서대로 돌아다닐 수 있다.
단, 맛집을 중복해서 갈 수는 없다.
맛집들의 타이틀 음식 정보가 주어졌을 때, 기문이가 갈 수 있는 최대 맛집 개수를 구하여라.
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 맛집의 수 N(1≤N≤100)이 주어진다.
둘째 줄부터 N개의 줄에 걸쳐서 각 타이틀 음식을 이해하기 필요한 이해력, 소화력과 이해했을 경우에 얻을 수 있는 점수가 순서대로 주어진다.
이 숫자는 모두 1,000 이하의 자연수이다.
[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 기문이가 갈 수 있는 맛집의 최대 개수를 구하여라.
입력 예제
2
5
1 3 1
10 20 5
3 3 1
3 1 1
1 1 1
3
2 2 1
2 3 1
3 2 1
// 테스트 케이스 개수
// 맛집의 수 N = 5
// 이해력 = 1, 소화력 = 3, 능력 점수 = 1
출력 예제
#1 4
#2 0
// 첫 번째 테스트 케이스 결과
- (즉, 미식왕의 이해력이 음식의 이해력보다 이상이거나, 소화력이 음식의 양보다 이상이어야 한다.) <- or로 되어 있는거 같습니다.
저는 둘중 하나만 만족하면 타이틀 점수를 얻을 수 있다고 풀고 있습니다만..잘못 이해한건지 안풀리네요.
아래와 같이 정렬한 후...즉, 9의 이해력만 있으면 모든 음식점을 클리어 할 수 있다고 생각하는데 그럼 너무 쉬운거 같기도 하고..
전체 케이스에 맞지 않네요..(8개/12개).. 제가 잘못 이해하는 부분이 있나요?
10
1 2 7
1 6 1
2 1 7
2 3 8
3 4 1
4 15 3
5 10 10
7 17 10
8 4 1
9 13 6
칸 2017-11-03 18:01:38 좋아요 0
댓글- 이해하신게 맞긴 한데, 모든 음식점을 클리어 할 수 있는지 없는지 구하는게 아니라 클리어 할 수 있는 최대 음식점 수를 구하는거라서요.
예를 드신 건 필요한 이해력&소화력이 너무 작고 타이틀점수는 너무 많이 주는 best input 이라서. 조금 더 worst input 을 생각해보시면 좋을듯요.
어떤걸 먹었을 때 얻은 타이틀을 어느쪽으로 배치하느냐에 따라 다음 먹을 수 있는 종류가 달라지는데, 어떻게 나누어 배치해서 어떤걸 먹느냐에 따라 얻을 수 있는 타이틀점수도 다르고 이후 상황도 계속 달라지니까요.
3
1 1 4
4 8 2
8 5 10
간단하게 이런 경우는 앞에꺼만 정렬해서 순서대로 먹으면 마지막껀 못먹겠죠.
5
1 1 4
4 8 2
8 5 10
1000 9 1
8 1000 1
그리고 이런 경우라면 중간에 획득한 타이틀점수를 배분까지 적절하게 잘 해야 다 먹을 수 있겠죠?
#include<stdio.h>#include<iostream>usingnamespacestd;boolvisit[100];intdata[100][3];intresult = 0;intn;voidcal(intX,intY,intcnt){result = result > cnt ? result : cnt;intvisit_t[100];for(inti = 0; i < n; i++) visit_t[i] = visit[i];boolchange =false;intpoint = 0;for(inti = 0; i < n; i++){if(visit[i] ==false){if(X >= data[i][0] || Y >= data[i][1]){change = visit[i] =true;point += data[i][2];cnt++;}}}if(change){cal(X + point ,Y,cnt);cal(X,Y + point ,cnt);}for(inti = 0; i < n; i++) visit[i] = visit_t[i];}intmain(){intT;scanf("%d",&T);for(inttest = 1; test <= T; test++){result = 0;scanf("%d", &n);for(inti = 0; i < n; i++){scanf("%d %d %d", &data[i][0], &data[i][1], &data[i][2]);}cal(1,1,0);printf("#%d %d\n", test, result);}}
- (즉, 미식왕의 이해력이 음식의 이해력보다 이상이거나, 소화력이 음식의 양보다 이상이어야 한다.) <- or로 되어 있는거 같습니다.