저울 C++(그리디, 탐욕법)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

https://programmers.co.kr/learn/courses/30/lessons/42886

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

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 + 테스트 코드

4. 결과

---

1. 문제 설명

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

문제!!

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

 

제한사항

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

 

예시

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

 

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

 

---

2. 문제풀이

이 문제는 프로그래밍 기술보다는 수학적으로 접근을 해야합니다. 물론 저도 풀지 못했기때문에 다른사람의 풀이를 보고 풀게 되었습니다. 접근 방법에 대해서는 아래 적도록 하겠습니다. 추 가 {3, 1, 6, 2, 7, 30, 1}이라고 하자 정렬후 {1, 1, 2, 3, 6, 7, 30}이 된다. 이걸 오름차순 정렬 후 앞부터 더한 값과 비교를 한다. 주의 해야 할점은 answer-1은 앞의 추로 만들수 있는 최대의 수이다. 1,1,2,3의 추를 이용하면 7까지 모든 경우의 수를 만들 수 있다. 4 = 2 + 1 +1 5 = 2 + 3 6 = 3 + 2 + 1 7 = 3 + 2 + 1 + 1 만약 지금까지 더 한값(추)보다 더 큰 추가 나온다면 answer는 만들 수 없는 수이다. 처음 answer 를 0으로 두면 반환전에 +1을 해서 반환해야 한다.

 

---

3. 소스코드

3.1 주석없는 코드

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> weight) {
    int answer = 1;
    sort(weight.begin(), weight.end());
    for (auto w : weight) {
        if (answer < w)        break;
        answer += w;
    }
    return answer;
}

3.2 주석 + 테스트 코드 추가

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> weight) {
    //1부터 비교를 시작
    int answer = 1;
    sort(weight.begin(), weight.end());
    /*
    ex) 백터가 {3, 1, 6, 2, 7, 30, 1}이라고 하자
    정렬후 {1, 1, 2, 3, 6, 7, 30}이 된다.
    이걸 오름차순 정렬후 앞부터 더한 값과 비교를 시작
    주의 해야 할점은 answer-1은 앞의 추로 만들수 있는 최대의 수이다.
    1,1,2,3의 추를 이용하면 7까지 모든 경우의 수를 만들 수 있다.
    4 = 2 + 1 +1
    5 = 2 + 3
    6 = 3 + 2 + 1
    7 = 3 + 2 + 1 + 1
    만약 지금까지 더한수보다 더 큰 추가 나온다면 answer는 만들 수 없는 수이다.
    */
    for (auto w : weight) {
        if (answer < w)        break;
        answer += w;
    }
    return answer;
}
 
void print(vector<int> weight, int answer){
    int t = solution(weight);
    if (answer == t)    cout << "정답" << endl;
    else    cout << "틀림" << endl;
}
 
int main(){
    print({ 3,1,6,2,7,30,1 }, 21);
    return 0;
}

 

4. 결과