[BEAKJOON/ 백준] 2629번: 양팔저울 (Python)

 

---

[1] 정답 코드

 

import sys

n = int(sys.stdin.readline())
weight = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
check = list(map(int, sys.stdin.readline().split()))
possible = []
ans = [[0 for _ in range(15001)] for __ in range(n + 1)]


def scale(weight, n, now, left, right):
    new = abs(left - right)
    if new not in possible:
        possible.append(new)
    if now == n:
        return 0
    if ans[now][new] == 0:
        scale(weight, n, now + 1, left + weight[now], right)
        scale(weight, n, now + 1, left, right + weight[now])
        scale(weight, n, now + 1, left, right)
        ans[now][new] = 1


scale(weight, n, 0, 0, 0)
for i in check:
    if i in possible:
        print('Y', end=' ')
    else:
        print('N', end=' ')

 

---

[2] 설명

 

import sys

n = int(sys.stdin.readline())
weight = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
check = list(map(int, sys.stdin.readline().split()))
possible = []
ans = [[0 for _ in range(15001)] for __ in range(n + 1)]

 

 

1. n = int(sys.stdin.readline()): 첫 번째 줄에서 정수를 읽어들여 변수 n에 할당한다. n은 추의 개수를 나타낸다.

2. weight = list(map(int, sys.stdin.readline().split())): 다음 줄에서는 공백으로 구분된 정수를 읽어들여 리스트 weight에 저장한다. weight는 각 추의 무게를 의미한다.

3. m = int(sys.stdin.readline()): 그 다음 줄에서는 또 다른 정수를 읽어들여 변수 m에 할당한다. 이 값은 확인할 무게들의 개수를 나타낸다.

4. check = list(map(int, sys.stdin.readline().split())): 그 다음 줄에서는 다시 공백으로 구분된 정수를 읽어들여 리스트 check에 저장한다. 이는 확인할 무게들을 나타낸다.

5. possible = []: 가능한 모든 조합을 저장할 빈 리스트 possible을 초기화한다.

6. ans = [[0 for _ in range(15001)] for __ in range(n + 1)]: 가능한 모든 무게 차이를 기록할 이중 리스트 ans를 초기화한다. 이 이중 리스트의 크기는 (n+1) × 15001이다.

 

---

sys.stdin.readline() 함수

 

sys.stdin.readline() 함수는 Python의 sys 모듈에서 제공되는 함수로, 표준 입력에서 한 줄을 읽어들인다. 이 함수는 표준 입력(stdin)에서 문자열을 읽어들여 반환한다.

보통 파일 객체에서 사용되는 readline() 메서드와 유사하지만, 이 함수는 파일이 아닌 표준 입력(stdin)에서 데이터를 읽어들인다. 표준 입력(stdin)은 보통 터미널에서 사용자로부터 입력된 데이터를 의미한다.

예를 들어, 터미널에서 사용자로부터 문자열을 입력받아 처리하고자 할 때, sys.stdin.readline()을 사용하여 입력을 읽어들일 수 있다. 이 함수는 개행 문자('\n')를 포함한 문자열을 반환하므로, 필요에 따라 문자열을 처리할 때 이를 제거하는 등의 작업을 추가로 수행해야 할 수 있다.

 

예를 들어,

import sys

# 표준 입력에서 한 줄을 읽어들임
input_str = sys.stdin.readline()

# 개행 문자를 제거한 문자열을 출력
print(input_str.strip())

 

이 코드는 표준 입력에서 한 줄을 읽어들여 변수 input_str에 저장한 후, strip() 메서드를 사용하여 문자열의 양쪽 공백과 개행 문자를 제거한 후 출력한다.

 

 

---

이중 리스트

 

이중 리스트란 리스트 안에 리스트가 포함된 형태를 말한다. 즉, 리스트의 원소로서 리스트를 가지고 있는 구조를 말한다. 이를 통해 다차원의 데이터를 표현할 수 있다.

예를 들어, 이차원 배열이나 행렬을 표현할 때 사용된다. 이중 리스트의 각 요소는 다른 리스트이므로, 이를 통해 각 행과 열의 원소에 접근할 수 있다.

 

다음은 이중 리스트의 예시이다.

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

 

위의 예시에서 matrix는 이중 리스트이며, 각 요소는 다른 리스트이다.

 

첫 번째 요소 matrix[0]는 [1, 2, 3]이고, 두 번째 요소 matrix[1]는 [4, 5, 6]이다. 따라서 matrix[행][열]의 형태로 각 요소에 접근할 수 있다.

이중 리스트는 데이터를 행렬 형태로 표현할 때 주로 사용되며, 다차원의 데이터를 다룰 때 효과적이다. 예를 들어, 이미지나 비디오 데이터를 다룰 때 각 픽셀의 색상 값을 이중 리스트로 표현하는 등의 활용이 가능하다.

 

 

def scale(weight, n, now, left, right):
    new = abs(left - right)
    if new not in possible:
        possible.append(new)
    if now == n:
        return 0
    if ans[now][new] == 0:
        scale(weight, n, now + 1, left + weight[now], right)
        scale(weight, n, now + 1, left, right + weight[now])
        scale(weight, n, now + 1, left, right)
        ans[now][new] = 1

 

 

위의 코드는 가능한 조합을 찾는 재귀 함수인 scale을 정의하는 부분이다.

 

1. scale(weight, n, now, left, right): 함수의 매개변수로는 추의 무게를 담은 리스트 weight, 추의 개수 n, 현재 처리 중인 추의 인덱스 now, 왼쪽 저울에 올라간 추의 무게 합 left, 오른쪽 저울에 올라간 추의 무게 합 right가 있다.

 

2. new = abs(left - right): 현재 왼쪽 저울과 오른쪽 저울에 올라간 추들의 무게 차이를 계산하여 new에 저장한다. 음수일 경우를 대비하여 abs()를 사용한다.

3. if new not in possible: possible.append(new): 새로 계산한 무게 차이가 possible 리스트에 없는 경우, 새로운 무게 차이를 possible 리스트에 추가한다. 이렇게 함으로써 중복된 무게 차이를 방지한다.

4. if now == n: return 0: 현재 처리 중인 추의 인덱스가 추의 개수와 같은 경우, 즉 모든 추에 대한 처리가 끝난 경우에는 더 이상 재귀 호출을 하지 않고 함수를 종료한다.

5. if ans[now][new] == 0: ... ans[now][new] = 1: 이중 리스트 ans를 사용하여 이미 계산한 무게 차이인지 확인한다. 만약 해당 무게 차이가 계산되지 않은 경우라면, 새로운 추를 왼쪽 저울에 올리는 경우, 오른쪽 저울에 올리는 경우, 혹은 올리지 않는 경우를 각각 재귀적으로 호출하여 가능한 모든 조합을 계산한다. 그리고 해당 무게 차이의 인덱스에 1을 할당하여 중복 계산을 방지한다.

이 함수를 통해 가능한 모든 무게 차이를 계산하고 possible 리스트에 저장하게 된다.

 

 

 

scale(weight, n, 0, 0, 0)
for i in check:
    if i in possible:
        print('Y', end=' ')
    else:
        print('N', end=' ')

주어진 코드는 scale 함수를 호출하여 가능한 모든 무게 차이를 계산하고, 이를 바탕으로 각 확인할 무게에 대해 가능한지 여부를 출력하는 부분으로 이루어져 있다. 아래에서 각 부분을 자세히 설명하겠다.

1. scale(weight, n, 0, 0, 0): 이 부분은 scale 함수를 호출하여 가능한 모든 무게 차이를 계산한다. 이 때, weight는 주어진 추의 무게를 담은 리스트이며, n은 전체 추의 개수이다. 0은 현재 처리 중인 추의 인덱스를 나타내며, 0은 왼쪽 저울과 오른쪽 저울에 올라간 추의 초기 무게 합을 의미한다. 이 호출을 통해 possible 리스트에 가능한 모든 무게 차이가 저장된다.

2. for i in check:: 이 부분은 확인할 무게들에 대한 반복문이다. check 리스트에 있는 각 무게를 순회한다.

3. if i in possible:: 이 부분은 현재 확인 중인 무게 i가 possible 리스트에 있는지 여부를 확인한다. 즉, 주어진 추의 무게로 가능한 무게 차이 중에 현재 확인 중인 무게가 있는지를 검사한다.

4. print('Y', end=' ')와 print('N', end=' '): 이 부분은 가능한 경우에는 'Y'를 출력하고, 그렇지 않은 경우에는 'N'을 출력한다. 여기서 end=' '는 출력 후 줄 바꿈 대신에 공백을 추가하는 옵션이다.

따라서 주어진 코드는 가능한 모든 무게 차이를 계산한 뒤, 각 확인할 무게에 대해 가능한지 여부를 판단하여 출력하는 것을 목적으로 한다.

 

---

[3] 느낀 점

 

한 줄에 여러 문자를 입력받는 함수인 'sys.stdin.readline()'에 대해서도 이번 기회로 처음 알게 되었다.

문법도 몰랐지만, 로직도 떠올리지 못해서 많이 어려웠던 문제였다.

 

하지만 이렇게 공부하다보면 실력이 조금씩이라도 늘지 않을까?

그랬으면 좋겠다...

 

---

[4] 참고

 

https://ca.ramel.be/72