17279번 - 홀수 부분열 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 117 | 40 | 26 | 33.333% |
문제
길이 n인 음이 아닌 정수로 이루어진 배열 A에 대해, 0개 이상의 원소를 지워서 얻을 수 있는 배열을 "부분열"라고 한다.
배열 A의 부분열 S에 대해, S가 다음 조건을 만족하면 S를 A의 "홀수 부분열"이라고 정의한다:
- S의 원소의 합의 자릿수 중 홀수인 것들이 홀수이다.
음이 아닌 정수 배열 A를 입력받아 A의 서로 다른 홀수 부분열의 개수를 출력하시오. 단, 부분열의 원소들을 정렬했을 시 그 결과가 같다면 같은 부분열로 취급한다.
A = [3, 3, 6, 8, 6] 경우 정답은 8이다.
- 길이가 0인 홀수 부분열: X
- 길이가 1인 홀수 부분열: [3]
- 합이 3, 자릿수 중 홀수가 3으로 하나
- 길이가 2인 홀수 부분열: [3, 6], [6, 6], [6, 8]
- 합이 각각 9, 12, 14로 자릿수 중 홀수가 9, 1, 1로 하나씩
- 길이가 3인 홀수 부분열: [3, 3, 6], [3, 3, 8]
- 길이가 4인 홀수 부분열: [3, 3, 6, 6], [3, 6, 6, 8]
- 길이가 5인 홀수 부분열: X
입력
첫 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 10).
각 테스트 케이스에 대해 첫 줄에 A의 길이 n 이 주어진다. 둘째 줄에 n개의 0이상의 정수가 공백으로 구분되어 주어진다. A의 각 원소는 0 이상 2,000 이하이다.
출력
각 테스트 케이스에 대해 홀수 부분열의 수를 한 줄에 출력한다.
서브태스크 1 (3점)
- 1 ≤ n ≤ 10
서브태스크 2 (11점)
- 1 ≤ n ≤ 60
예제 입력 1
3 3 3 3 6 4 0 1 2 3 5 3 3 6 8 6
예제 출력 1
3 8 8
힌트
- 테스트 케이스 1: {3}, {3,6}, {3, 3, 6} 세 종류의 홀수-부분열이 있다.
- 테스트 케이스 2: {1}, {3}, {0,1}, {0,3}, {1,2}, {2,3}, {0,1,2}, {0,2,3} 여덟 종류의 홀수-부분열이 있다.
- 테스트 케이스 3: 문제에서 서술된대로 여덟 종류의 홀수-부분열이 있다.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호