https://www.acmicpc.net/problem/12970
풀이 아이디어
문자열의 길이에 따라 A와 B로 만들 수 있는 조합의 최대 개수가 정해져있다. 직접 여러 길이의 문자열을 만들어가며 풀이할 때 알게 된 특징이다.
길이가 10인 문자열로 만들 수 있는 조합의 최대 개수는 AAAAABBBBB로, 5*5=25개이다.
길이가 11인 문자열로 만들 수 있는 조합의 최대 개수는 AAAAAABBBBB → 5*6=30 or AAAAABBBBBB → 6*5=30
길이가 30인 문자열로 만들 수 있는 조합의 최대 개수는 15A15B → 15*15=225최대 개수의 공식은 $ \lfloor\frac{N^2}{4}\rfloor $ 이다.
그렇다면 최소 개수는 몇 개일까? 당연히 0개이다. 모든 길이에 대해서 A 혹은 B 문자 하나로만 나열한다면, 그 값은 0이 된다.
혹은 BBBBBAAA처럼 모든 B가 A보다 앞에 나열되어 있다면, 이 경우도 값은 0이다. 하지만 이런 경우를 따지기엔 더 쉬운 경우가 있다. 그래서 내가 문제를 풀 때는 고려하지 않았다.
나는 문자열에서 AB의 나열을 적절히 하면 0부터 최대 개수 사이의 모든 수를 표현할 수 있음을 알았다.
길이가 5인 문자열을 보자. →$ \lfloor\frac{5^2}{4}\rfloor $ 이므로 최대 개수는 6개이다.
AAAAA → 0
BAAAA → 0
ABAAA → 1
AABAA → 2
AAABA → 3
..
ABAAB → 2*1 + 1*2 = 4
AABAB → 2*2 + 1*1 = 5
AAABB → 2*3 = 6
이렇게 0부터 조합의 최대 개수 까지 모든 수를 찾을 수 있다.
이 문제는 주어진 숫자를 만들 수 있는 아무 AB문자열을 출력해야 하므로, 0부터 순서대로 AB문자열을 만들고 검사하는 방식으로 문제를 해결하려고 했다. 부르트포스인 셈이다.
풀이👀
- 'A'와 'B'의 최대 조합의 수를 계산하기 위해 get_max_spares(n)를 정의한다.
- 0부터 최대 개수까지 모두 찾는 비효율적인 경우를 대비하기 위해 get_start(n, target)를 정의합니다. 이 함수는 주어진 조건을 만족하는 문자열의 최대 시작 위치를 찾는다.
(예를 들어 10 12 가 입력으로 들어온 경우, AAAAAAAAAA(0) 보다 AAAAAAAAAB(9) 부터 찾기 시작하는 것이 목표한 12를 더 빨리 찾을 수 있을 것이다.) - 문자열 내에서 'A'와 'B'의 이웃한 조합 수를 계산하기 위해 get_spares(string)를 정의합니다.
- 주어진 입력 값으로부터 조건을 만족하는 문자열을 생성합니다. 먼저, 최대 가능한 조합 수를 확인하고, 조건을 만족하는 시작 위치를 찾는다. 그 후, 문자열을 생성하고, 조건을 만족할 때까지 문자열을 변경한다.
- 주어진 문자열에서 'B'의 위치를 이동시켜 조건을 만족하는 문자열을 생성하기 위해 change(string, idx)를 정의한다.
코드🐱👓
def get_max_spares(n):
return int(n**2 / 4)
def get_start(n, target):
for i in range((n+1)//2):
if i*(n-i) <= target and target <= (i+1)*(n-i-1):
return i
def get_spares(string):
cnt = 0
for i in range(len(string)):
if string[i] == 'B':
continue
for j in range(i+1, len(string)):
if string[j] == 'A':
continue
cnt+=1
return cnt
def change(string, idx):
if idx+1 < len(string) and string[idx] == 'B' and string[idx+1] == 'A':
string[idx], string[idx+1] = string[idx+1], string[idx]
return idx+1
string[0] = 'B'
return 0
n, k = map(int, input().split())
if get_max_spares(n) < k:
print(-1)
else:
tmp1 = get_start(n, k)
string = ['A']*(n-tmp1) + ['B']*tmp1
idx = 0
while get_spares(string) != k:
idx = change(string, idx)
print(*string, sep = '')
'문제 풀이 > 백준' 카테고리의 다른 글
[S3] 백준 1463 - 1로 만들기(Python) (0) | 2024.09.05 |
---|---|
[G5] 백준 11729 - 하노이 탑 이동 순서 (Python3) (0) | 2024.05.04 |
[S1] 백준 2156 - 포도주 시식 (Python3) (0) | 2024.04.28 |
[S1] 백준 1149 - RGB거리 (Python3) (0) | 2024.04.28 |
[S1] 백준 1932 - 정수 삼각형 (Python3) (0) | 2024.04.27 |
댓글