29768-펠린드롬 이름

https://www.acmicpc.net/problem/29768

팰린드롬 이름

성공

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

문제

팰린드롬의 마법사 엣지는 오늘도 팰린드롬을 찾고 있었다. 그러던 도중 팰린드롬을 좋아하는 사람들이 모이는 축제를 만들고 싶어졌다. 축제의 이름의 길이는 \(N\)이고 이름은 서로 다른 영어 알파벳 소문자 \(K\)가지로 이루어져 있어야 한다. 마법사 엣지는 축제 이름의 조건을 만족하면서 서로 다른 부분 문자열 중 팰린드롬의 개수가 가장 많은 문자열을 축제의 이름으로 정한다. 문제에 사용된 단어의 의미는 예제 아래에 위치한 노트를 참고하자.

마법사 엣지를 위해 축제의 이름을 하나 만들어주자. 축제의 이름으로 정할 수 있는 이름이 여러 개라면, 사전순으로 가장 앞선 이름을 만든다.

입력

첫째 줄에 이름의 길이 \(N\)과 알파벳 소문자의 개수 \(K\)가 공백으로 구분되어 입력된다. \((1 \leq N \leq 100\,000, 1 \leq K \leq 26, K \leq N)\)

출력

첫째 줄에 마법사 엣지가 정할 축제의 이름을 출력한다.

예제 입력/출력

예제 입력 1

1 1
        

예제 출력 1

a
        

예제 입력 2

2 1
        

예제 출력 2

aa
        

예제 입력 3

2 2
        

예제 출력 3

ab
        

노트

팰린드롬은 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어 level은 팰린드롬이지만, apple은 아니다.

부분 문자열이란 문자열에서 연속한 문자 몇 개를 이어 붙인 문자열을 뜻한다. 예를 들어 aba의 부분 문자열은 a, b, a, ab, ba, aba가 있다.

두 부분 문자열 \(A\), \(B\)가 서로 다르다는건 두 부분 문자열의 길이가 다르거나, \(A\)의 \(i\)번째 글자와 \(B\)의 \(i\)번째 글자가 다르게 하는 어떤 \(i\)가 존재함을 뜻한다. 서로 다른 부분 문자열이란 부분 문자열 중 서로 다른 것들이다. 예를 들어 aba의 서로 다른 부분 문자열은 a, b, ab, ba, aba이다.

사전순은 사전에 쓰이는 문자열의 배열 순서를 말한다. 예를 들어 abc는 acb보다 사전순으로 앞섰고, aa는 aaa보다 사전순으로 앞섰다.

 

문제 이해

길이 N인 문자열을 영어 소문자 K종류를 모두 사용하여 만들고, 그 문자열의 서로 다른 팰린드롬 부분 문자열 개수를 최대화해야 합니다. 팰린드롬이란 앞뒤가 같은 문자열이고, 부분 문자열은 연속한 문자의 집합이며, 서로 다른 부분 문자열의 개수를 셉니다. 여러 개의 후보가 있다면 사전순으로 가장 앞서는 문자열을 출력해야 합니다.

핵심 아이디어

1. 팰린드롬 부분 문자열을 많이 만들려면 중복되는 문자 구간을 최대로 늘려야 합니다. 즉, 같은 문자가 연속될수록 ‘a’, ‘aa’, ‘aaa’… 와 같은 팰린드롬이 많이 생깁니다.
2. 하지만 반드시 K개의 서로 다른 알파벳을 모두 사용해야 하므로, 문자열 끝부분에 남은 K−1개의 서로 다른 문자를 한 번씩 배치해야 합니다.
3. 따라서 앞부분에 a를 가능한 한 많이 반복하고, 뒤에 b, c, … 순으로 한 번씩 붙이는 형태가 최적입니다.

수식화

• 전체 길이: N
• 서로 다른 알파벳 수: K (최소 하나씩 사용) → 나머지는 모두 같은 문자로 채움
• 같은 문자로 채우는 길이: r = N − (K − 1)

따라서 정답 문자열은

ar + “b c … (K−1번째 문자)”

즉,

“a”를 (N−K+1)번 반복한 뒤,
“b”, “c”, …, (char)('a'+K−1)을 각각 한 번씩 붙인다.

코드 구현

import sys
input = sys.stdin.readline

def solve():
    N, K = map(int, input().split())
    # 1) a를 가능한 많이: N - (K - 1) 번
    a_count = N - K + 1
    # 2) 남은 K-1개의 다른 문자
    tail = ''.join(chr(ord('a') + i) for i in range(1, K))
    # 결과 출력
    print('a' * a_count + tail)

if __name__ == "__main__":
    solve()

동작 예시

• 예제 1: N=1, K=1 → r=1, 문자열 “a”
• 예제 2: N=2, K=1 → r=2, 문자열 “aa”
• 예제 3: N=2, K=2 → r=1, 앞에 “a” 하나, 뒤에 “b” → “ab”

결론

이 방식은 O(N+K) 시간에 문자열을 만들어 냅니다. 연속된 동일 문자로 최대한 많은 팰린드롬을 확보하고, 필요한 만큼 서로 다른 문자를 뒤에 배치하여 모든 조건을 만족하는 최적해입니다.

def s():
    n,k=map(int,open(0).read().split())
    r=n-k+1
    print('a'*r+''.join(chr(97+i) for i in range(1,k)))
s()