2주차_백준 (2) - 양팔저울

▶문제

문제 조건이 많다. 조건부터 정리해보자면

① 추의 개수 : 자연수, 30개 이하

② 추의 무게: 자연수, 500g이하, 같은 무게의 추 중복 가능

③ 무게를 확인하고자 하는 구슬의 개수: 7개 이하

④ 확인하고자 하는 구슬의 무게: 40,000보다 작거나 같은 자연수

줄별로 크게 4가지로 나눌 수 있다.

​

​

​

▶풀이

문제를 살펴보면 양팔 저울이 무게를 재는 원리는 "양팔에 올라간 추의 무게 차이"임을 알 수 있다.

이 문제 또한 시간 안에 풀기 위해서는 중복되는 경우가 있는지 생각해봐야 한다. 고민해본 결과 양팔의 차이가 같은 경우들은 굳이 중복해서 계산하지 않아도 되지 않을까?라는 생각을 해보았다.

예를 들자면 <그림 1>과 같이 1g&4g 추로 구슬의 무게가 3g임을 알 수 있지만 2g&5g, 극단적으로 97g&100g이어도 구슬의 무게는 3g일 것이다.

즉, 좌우 차이만 동일하다면 같은 무게를 측정하고 있기에 중복되는 것이다. 이렇게 중복 부분 문제가 발생하기 때문에 이 문제도 DP를 통해 해결할 수 있다.

전체 코드

<코드별 해석>

​

① 1~8번째 줄: 입력을 받고, 필요한 변수들을 초기화한다.

• weight: 저울의 무게를 저장하는 리스트
• check: 확인해야 할 무게를 저장하는 리스트.
• possible: 가능한 무게 조합을 저장할 리스트
• ans: 이미 확인한 무게 조합인지를 확인하기 위한 이차원 배열

​

※이차원 배열 선언 방법

① 2중 for문으로 2중 리스트 선언

② 연산자와 for문으로 리스트 선언

여기선 1번 방식으로 선언해주었다.

​

② 10~20번째 줄: scale이라는 이름의 함수를 정의한다. 각 단계에서 현재까지의 왼쪽 무게와 오른쪽 무게를 비교하여 새로운 무게를 계산하고, 가능한 무게 조합을 possible 리스트에 추가한다.

​

③ 22번째 줄: scale 함수를 호출하여 가능한 무게 조합을 모두 탐색한다.

​

④ 23~27번째 줄: 마지막으로 해당 무게가 가능한지 여부를 확인하고 출력한다. 가능하면 'Y'를, 불가능하면 'N'을 출력한다.

1520번 내리막길 문제보단 조금 더 이해하기 쉬웠다. DP와 리스트 개을 다시 한 번 짚고 넘어갈 수 있었다.