[백준/파이썬]28292 개미 수열

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

28292번: 개미 수열

 

문제

대구 소프트웨어 마이스터고 대회 문제다.

 

처음에 구현할 때 저기 적힌 대로 그대로 구현했다.

 

오답

n = int(input())

arr = ['1']
for i in range(n-1) :
    for s in arr :
        count = 0
        new_arr = ''
        for j in range(len(s)) :
            if j == 0 :
                first_char = s[j]
                count += 1
            else :
                if s[j] != first_char :
                    new_arr += first_char + str(count)
                    first_char = s[j]
                    count = 1
                else :
                    count += 1

        new_arr += first_char + str(count)
    arr.append(new_arr)
max_num = -1
for c in arr[n-1] :
    if int(c) > max_num :
        max_num = int(c)
print(max_num)

그런데 시간초과가 나오는게 아닌가?

 

그래서 너무 정직하게 하란대로 짰나 싶어 DP로 짜야하는 건가라고 곰곰이 생각하다가 알고리즘 분류를 봤다.

 

 

애드 혹?

 

이게 뭔가 싶어 또 구글한테 물어봤더니

 

 

 

이렇게 대답해줬다.

 

대충 문제 해결을 위해 완전 다른 방식으로 접근하는 효율적인 알고리즘이라는 것 같다.

 

어쩐지 문제에서 N번째 수열을 출력하라는 게 아니라 N번째 수열에서 가장 큰 수를 출력하라는게 의심스럽긴 했다.

 

그래서 예시 입출력을 보고 몇 가지 가정을 했다.

 

1. 2의 제곱에 어떤 규칙이 있나?

2. 3보다 큰 값이 나올 수 없는가?

 

정답은 2번이었다.

 

개미 수열에서 3보다 큰 수는 나올 수가 없었다. 

 

왠진 모르겠다. 증명은 못하겠지만 수열을 계속 만들어봐도 1로 시작했을 때 4 이상은 만들어지지 않았다.

 

즉 저 문제에서 입력 값이 6 이상일 땐 3만 출력해 주면 된다...

 

1, 11, 12, 1121, 122111, 112213, 12221131, 1123123111, .....

 

정답

n = int(input())

arr=[1, 1, 2, 2, 2, 3]

if n >= 6 :
    print(arr[-1])
else :
    print(arr[n-1])

 

 

 

반응형