21979번 - 16진수 쪼개기
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 40 | 21 | 19 | 76.000% |
문제
길이가 n인 문자열 S를 아래 조건에 따라 k개의 부분문자열 (substring) T1, T2, ..., Tk로 쪼개는 경우를 생각해보자:
- 1 ≤ k ≤ n
- 1 ≤ i ≤ k를 만족하는 i에 대하여 각 부분문자열 Ti는 길이 1 이상이며 S의 부분문자열이다 (즉, S를 구성하는 연속한 문자들로 구성되어있다).
- T1, T2, ..., Tk 를 순서대로 이어붙이면 (string concatenation) 원래의 문자열 S가 된다.
예를 들어 S = "FED" 인 경우 아래와 같은 총 4가지의 방법으로 쪼갤 수 있다:
방법 1: T1 = "FED" (이 경우, k = 1)
- 방법 2: T1 = "F", T2 = "ED" (이 경우, k = 2)
- 방법 3: T1 = "FE", T2 = "D" (이 경우, k = 2)
- 방법 4: T1 = "F", T2 = "E", T3 = "D" (이 경우, k = 3)
참고로 길이가 n인 문자열을 위 조건대로 쪼개는 방법은 총 2n-1 가지 존재한다.
이 문제에서는 원래의 문자열 S가 0-9와 A-F로만 구성된 16진수라 가정한다.
Albert는 위 조건대로 S를 쪼개서 T1, T2, ..., Tk가 비감소수열이 (non-decreasing sequence) 되는 경우가 몇 가지나 되는지 알고 싶다.
구체적으로, Albert는 S를 쪼갠 후 각 부분 문자열이 타나내는 16진수 값이 T1 ≤ T2 ≤ ... ≤ Tk 를 만족하도록 하고 싶다.
위 예제의 경우, 상기한 네 가지 방법을 통해 만들어지는 수열은 아래와 같다:
- 방법1: [FED(16) = 4077] (비감소수열)
- 방법2: [F(16) = 15, ED(16) = 237] (비감소수열)
- 방법3: [FE(16) = 254, D(16) = 13]
- 방법4: [F(16) = 15, E(16) = 14, D(16) = 13]
이 경우 비감소수열은 방법1, 방법2을 통해 얻을 수 있으므로 답이 2가 된다.
다른 예로 S = "0070"인 경우, 아래와 같은 4가지 방법이 가능하다.
- 방법 1: T1 = "0070"
- 방법 2: T1 = "0", T2 = "0", T3 = "70" (이 경우 [0, 0, 70(16) = 112] 이다)
- 방법 3: T1 = "00", T2 = "70"
- 방법 4: T1 = "0", T2 = "070"
방법1, 방법3, 방법4에서 보이듯 부분 문자열이 선행 0을 (leading zero) 포함하는 것도 허용된다.
입력으로 16진수 문자열 S가 주어졌을 때, Albert가 몇 가지 방법으로 S를 부분 문자열로 쪼개서 비감소수열을 얻을 수 있는지 구해보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
다음 각 줄에 문자열 S가 주어진다.
문자열 S를 구성하는 문자는 16진법에 사용되는 0-9 (숫자)와 A-F (영대문자) 뿐이다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
제한
- 1 ≤ T ≤ 20
- 1 ≤ n ≤ 15
- S를 구성하는 문자는 0-9 와 A-F 뿐이다
예제 입력 1
4 0070 FED 42 002021
예제 출력 1
4 2 1 12
예제 1: 본문에서 다루었다.
예제 2: 본문에서 다루었다.
예제 3: [42]가 유일한 방법이다.
예제 4: 추가 설명 없음.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호