아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

막대로 정사각형 만들기

면접 대비

시간 제한1초메모리 제한128 MB

요약
길이가 서로 다른 막대 20개 이하가 주어질 때, 모든 막대를 네 변의 길이가 같은 네 그룹으로 나눌 수 있는지 판정한다.
난이도

보통10점 중 6점

유형
백트래킹, 재귀, 정렬, 완전 탐색
정답자
아직 제출이 없습니다

문제

길이가 서로 다를 수 있는 막대 NN개가 있다. 이 막대들을 모두 사용하여 정사각형의 네 변을 만들 수 있는지 판별하여라.

막대는 자를 수 없고, 각 막대는 정확히 한 변에만 사용해야 하며, 네 변의 길이가 모두 같아야 한다. 즉, 막대들을 길이의 합이 서로 같은 네 묶음으로 나눌 수 있으면 정사각형을 만들 수 있다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 각 테스트 케이스는 한 줄로 이루어진다. 그 줄의 첫 번째 정수는 막대의 개수 NN이다 (4≤N≤204 \le N \le 20). 이어서 막대의 길이를 나타내는 정수 NN개가 공백으로 구분되어 주어지며, 각 길이는 11 이상 1000010000 이하의 자연수이다.

출력

각 테스트 케이스마다 막대를 모두 사용해 정사각형을 만들 수 있으면 yes를, 만들 수 없으면 no를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    3
    4 1 1 1 1
    5 10 20 30 40 50
    8 1 7 2 6 4 4 3 5
    
    예상 출력
    yes
    no
    yes