BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/2437
2437번: 저울
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓
www.acmicpc.net
내가 작성한 코드
import sys
read = sys.stdin.readline
def read_data():
N = int(read().rstrip())
choos = list(map(int, read().rstrip().split()))
return N, sorted(choos)
N, choos = read_data()
target = 1
for k in choos:
if target < k:
break
target += k
print(target)
- 아래 설명된 규칙으로 구현
다른 사람이 작성한 코드
n = int(input())
arr = list(map(int,input().split())
arr.sort()
target =1
for i in arr:
if target<i:
break
target += i
print(target)
- 아래 블로그의 설명과 코드로 작성
https://codingpractices.tistory.com/76
[그리디 알고리즘6] 백준 2437 저울 파이썬
백준 2437 저울 📜 문제 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의
codingpractices.tistory.com
기억해야할 것
- 풀이
- 누적된 합 이하의 값은 모두 만들 수 있다는 점이 이해가지 않았습니다.
- 1, 2, 4, 8, 16의 합으로 16이하의 모든 자연수를 만들 수 있지만... 왜? - 아래 블로그에서 자세한 설명을 보고 이해할 수 있었습니다.
- 어떤 리스트로 이미 만들 수 있는 범위 = [0, k]
- 이 때, k는 누적값을 나타내게됨
- 이 리스트에 x를 추가하여 새로 만들 수 있는 범위 = [x, x+k]
- 따라서, k >= x이면, [0, x+k]까지 연속으로 만들 수 있음
- 누적된 합 이하의 값은 모두 만들 수 있다는 점이 이해가지 않았습니다.
백준 2437 풀이 및 해설
개요 매우 복잡해보이는 문제가 그림으로 풀면 매우 단순하게 풀리는 경우 는 그리 드문일이 아닙니다. 이 문제는 수학적 귀납법으로도 풀 수 있지만, 수직선을 사용하면 훨씬 직관적이고 쉽게
aerocode.net
'코딩테스트' 카테고리의 다른 글
[백준][구현] 마법사 상어와 복제 (0) | 2022.04.20 |
---|---|
[백준][구현] 어항 정리 (0) | 2022.04.19 |
[백준][투포인터] 냅색문제 (0) | 2022.04.08 |
[백준][그리디] 보석 도둑 (0) | 2022.04.01 |
[백준][재귀] 감소하는 수 (0) | 2022.04.01 |