프로그래머스 - 저울(Level 3)/Wanna Be 컴잘알

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42886#

코딩테스트 연습 - 저울 | 프로그래머스

 

-문제-

 

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 합니다. 이 저울의 양팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같습니다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있습니다.

저울추가 담긴 배열 weight가 매개변수로 주어질 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 return 하도록 solution 함수를 작성해주세요.

예를 들어, 무게가 각각 [3, 1, 6, 2, 7, 30, 1]인 7개의 저울추를 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21입니다.

제한 사항

• 저울추의 개수는 1개 이상 10,000개 이하입니다.
• 각 추의 무게는 1 이상 1,000,000 이하입니다.

입출력 예

weight	return
[3, 1, 6, 2, 7, 30, 1]	21

 

-접근-

 

1. 가장 작은 추의 무게가 2이상 일 때, 측정할 수 없는 양의 정수 무게 중 최솟값은 1이다. 따라서 answer의 초기값을 1로 세팅하였다.

2. 누적합보다 새로 더해야할 값이 더 크면 누적합을 return해준다. (누적합의 초기값이 0이 아닌 1이므로 누적합 자체가 추의 조합으로 만들 수 없는 양의 정수 값이된다.)

3. 예시로 주어진 케이스로 설명하자면 먼저 weight를 오름차순으로 정렬하면 [1, 1, 2, 3, 6, 7, 30]이 되고,

초기값 answer = 1

현재 값 weight[0]=1,  누적값=2

현재 값 weight[1]=1,  누적값=3

현재 값 weight[2]=2,  누적값=5

현재 값 weight[3]=3, 누적값=8

현재 값 weight[4]=6, 누적값=14

현재 갑 weight[5]=7, 누적값=21

// 현재까지 누적값이 21 인데, 1~20까지는 추의 조합을 가지고 만들 수 있음을 의미한다.

 

이때, 누적값보다 큰 30이 들어오는데 이 경우에 21~29의 수를 만들 수 없음을 의미한다.

따라서 만들 수 없는 최소값은 21이다.

(설명은 장황했지만 코드는 상당히 간단하다.)

 

-코드-

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> weight) {
	int answer = 1;
	sort(weight.begin(), weight.end());

	for (int i = 0; i < weight.size(); i++) {
		if (answer < weight[i])
			break;
		answer += weight[i];
	}
	
	return answer;
}