[백준] 2437 저울

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

처음에 비트마스킹을 이용하여 각 자릿수의 비트가 무게 하나로 생각하여 불가능한 무게를 구하는 방식을 이용하였습니다.

불가능한 무게를 구하기 위해서는 1비트씩 오른쪽으로 시프트 과정을 거치며 AND 연산을 통해 1의 여부 판별을 진행하였습니다.

그러나 입력에 따라 불가능한 무게를 탐색하는 과정이 매우 많이 필요하였고 그로 인해 시간 초과가 발생하였습니다.

 

추를 가장 가벼운 것부터 정렬하였고, 불가능한 최소 무게보다 작거나 같은 추가 있다면, 해당 무게는 측정이 가능하므로 다음 불가능한 무게로 갱신하였습니다.

그리고 불가능한 무게보다 큰 무게의 추가 나온다면 해당 무게는 측정이 불가능하므로 탐색을 종료하였습니다.

2) 알고리즘

• 정렬
• 그리디

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

# 입력데이터
N = int(sys.stdin.readline())
weights = sorted(list(map(int, sys.stdin.readline().split())))

# 불가능한 최소 무게
answer = 1

# 작은 무게의 추부터 시작
for w in weights:
    # 불가능한 최소 무게보다 현재 추가 더 무거우면 종료
    if answer < 1 << w-1:
        break

    # 불가능한 최소 무게 증가
    answer <<= w

print(len(bin(answer))-2)

---

🔗 문제 링크

- https://www.acmicpc.net/problem/2437

2437번: 저울

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다