프로그래머스 문제 풀이 저울

문제 URL 저울

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

자 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 입력입니다.

 

입력 :
weight = [3, 1, 6, 2, 7, 30, 1]

 

다음 무게를 지닌 추들로 측정할 수 없는 최소 무게를 찾아야 합니다. 먼저 손으로 풀어봅시다.

 

무게 = 1
w = 1 // 무게 1짜리 1개

 

이 때는 무게 1인 추 1개로 측정이 가능합니다.

 

무게 = 2
w = 2 = 1 + 1 // 무게 2 짜리 1개, 무게 1짜리 2개

 

무게 2는 무게 1짜리 추 2개 혹은 무게 2짜리 추 1개로 측정이 가능합니다.

 

무게 = 3
w = 3 = 1 + 2 // 무게 3짜리 1개, 무게 1짜리 1개 + 무게 2짜리 1개

 

무게 3은 무게 3짜리 추 1개 혹은 무게 2짜리 추 1개와 무게 1짜리 추 1개로 측정이 가능합니다. 다음은 각 무게에 따라서 측정 가능한 무게를 표현한 것입니다.

 

무게 = 4
w = 1 + 3 = 1 + 1 + 2

무게 = 5
w = 1 + 1 + 3 = 2 + 3

무게 = 6
w = 1 + 2 + 3 = 6

...

무게 20
w = 1 + 1 + 2 + 3 + 6 + 7

무게 21
측정 불가..

 

문제의 입력에서는 무게가 21일 때 처음으로 측정이 불가능합니다. 어떻게 문제를 풀 수 있을까요? 일단 제가 세운 방법은 "적은 무게부터 합치자"입니다. 무슨 소리냐면, 먼저 weight입력을 오름차순으로 정렬합니다.

 

weight = [1, 1, 2, 3, 6, 7, 30]

 

그리고 먼저 무게 1부터 시작합니다.

 

answer = 1

 

이후, weight를 무게들을 순회하며 answer 가 무게 w보다 크거나 같으면, answer에 w를 합쳐줍니다. 각 단계는 다음과 같습니다.

 

i = 0
w = 1
answer >= w 충족 (1 >= 1)
answer = 1 + 1 = 2// answer += w

i = 1
w = 1
answer >= w 충족 (2 >= 1)
answer = 2 + 1 = 3

i= 2
w = 2
answer >= w 충족 (3 >= 2)
answer = 3 + 2 = 5

i= 3
w = 3
answer >= w 충족 (5 >= 3)
answer = 5 + 3 = 8

i= 4
w = 6
answer >= w 충족 (8 >= 6)
answer = 8 + 6 = 14

i= 5
w = 7
answer >= w 충족 (14 >= 7)
answer = 14 + 7 = 21

i= 6
w = 30
answer >= w 불충족 (21 < 30)
answer = 21

 

어떻게 문제를 푸는 지 감이 오시나요?

 

이 문제는 "덧셈의 속성"을 이용하는 것입니다. 먼저 무게 1짜리 추 1개는 무게 1밖에 표현 못합니다. 그 후 무게 1짜리 추 2개로 무게 1, 2를 표현할 수 있습니다. 그 다음 무게 2짜리 추 1개 무게 1짜리 추 2개로 무게 1, 2, 3, 4를 표현 할 수 있습니다. 그러나 무게 5는 표현이 불가하지요.

 

그래서 추의 무게들을 합친 무게까지가 그 추들을 이용해서 측정할 수 있는 무게의 한계입니다. 즉 다음 수식이 성립됩니다.

 

추들의 무게의 합 + 1 = 추들이 측정할 수 없는 최소 무게

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

 

1. 입력 weight를 오름차순으로 정렬합니다.
2. answer = 1 부터 시작합니다.
3. weight를 순회합니다.
   1. answer >= w라면, answer에 w를 합칩니다.
4. answer를 반환합니다.

위의 알고리즘을 코드로 나타내면 다음과 같습니다. 먼저 PYTHON 코드입니다.

 

PYTHON 코드

def solution(weight):
    # 1. weight를 오름차순으로 정렬합니다.
    weight = sorted(weight)
    # 2. answer 1부터 시작합니다. 추의 최소 무게는 1입니다.
    answer = 1
    # 3. weight를 순회합니다.
    for w in weight:
        # 1. answer >= w라면, answer에 w를 더해줍니다.
        if answer >= w:
            answer += w
    # 4. answer를 반환합니다.
    return answer

 

다음은 CPP 코드입니다. 알고리즘은 동일합니다.

 

CPP 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

    for(auto w : weight) if (answer >= w) {
        answer += w;    
    }
    
    return answer;
}

 

추가적으로 반복문의 횟수를 줄이고 싶다면, answer < w가 나오는 순간에 반복문을 멈추면 됩니다. 하지만 위의 코드들로도 충분히 문제의 효율성 테스트를 통과하기 때문에, 저라면, 조금 더 보기 쉬운 위의 코드들을 사용할 것 같습니다.