[백준][그리디] 저울

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

2437번: 저울

 

내가 작성한 코드

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 저울 파이썬

기억해야할 것

• 풀이
  
  • 누적된 합 이하의 값은 모두 만들 수 있다는 점이 이해가지 않았습니다.
    - 1, 2, 4, 8, 16의 합으로 16이하의 모든 자연수를 만들 수 있지만... 왜?
  • 아래 블로그에서 자세한 설명을 보고 이해할 수 있었습니다.
    - 어떤 리스트로 이미 만들 수 있는 범위 = [0, k]
    - 이 때, k는 누적값을 나타내게됨
    - 이 리스트에 x를 추가하여 새로 만들 수 있는 범위 = [x, x+k]
    - 따라서, k >= x이면, [0, x+k]까지 연속으로 만들 수 있음

https://aerocode.net/392

백준 2437 풀이 및 해설