백준 28292 - 개미 수열

문제

대구소프트웨어마이스터고등학교에 다니고 있는 changwook987은 베르나르 베르베르의 소설 『개미』를 읽다가 흥미로운 수열을 보았다.

 1,11,12,1121 ... 

이 수열은 소설 『개미』에서 나와 개미 수열이라고 부르기도 하고 읽고 말하기 수열이라고 하기도 한다.

이 수열의 규칙은 이렇다.

1. 첫 번째 항은 1이다.
2. 이전 항의 이웃한 같은 숫자들을 묶는다.
   • 이전 항이 1121일 경우 (1,1), (2), (1)
3. 묶인 숫자들의 숫자와 개수를 붙여 쓴다.
   • 묶인 숫자들이 (1,1), (2), (1) 일경우 122111이 된다.
4. 2, 3을 반복한다.

이 개미 수열을 관찰하다 보면 수가 빠르게 길어지지만, 수를 이루는 숫자가 커지기는 쉽지 않다는 것을 알 수 있다.

그렇다면 이 수열의 N번째 항의 자릿수 중에서 가장 큰 수는 무엇일까?

개미 수열의 N번째 항의 자릿수 중 가장 큰 수를 출력해 보자.

입력

첫째 줄에 양의 정수 N이 주어진다. (1≤𝑁≤100)

출력

개미 수열의 N번째 항의 자릿수 중에서 가장 큰 수를 출력한다.

예제 입력 1 복사

1

예제 출력 1 복사

1

예제 입력 2 복사

2

예제 출력 2 복사

1

 

# 백준/실버5/개미 수열

N = int(input())


if N == 1 or N==2:
    print(1)
elif N == 3 or N == 4 or N == 5:
    print(2)
else:
    print(3)

 

신기한 문제였다.

 

일반 구현 문제인줄 알고 풀다가 시간초과로 풀리지가 않아 다른 사람들의 풀이를 검색했더니..

 

문제 조건에 N번째항의 자릿수 즉, 반복된 횟수가 아닌 숫자 자체의 최댓값을 구하는 문제였다.

 

근데 n이 6 이상이면 3을 넘지 못한다는 것이 문제의 포인트였다. 

 

결국 저런 코드가 나오게 된다..

 

구현으로 푼것도 아까워서 일단 남긴다.

 

# 백준/실버5/개미 수열
import collections

N = int(input())

ant = "1"

if N == 1:
    print(1)
else: 
    for _ in range(N-2):
        new_ant = ""
        cnt = 1
        prev = ""
        for i in range(0,len(ant)):
            if ant[i] == prev:
                cnt += 1
            elif ant[i] != prev and i!=0:
                new_ant += prev + str(cnt)
                cnt = 1
            
            prev = ant[i]
        
        new_ant += prev + str(cnt)
        ant = new_ant
        
    print(max(list(ant)))

 

나는 이전항을 활용했었다. 다음 항은 이전 항의 숫자 + 횟수 이기 때문에 이전 항의 숫자의 최대값이 곧 문제에서 원하는 최대값이 된다.