[백준알고리즘] 2661번: 좋은수열 -Python

[백준알고리즘] 2661번: 좋은수열 -Python

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

2661번: 좋은수열

한 번에 통과가 안돼서 오히려 당황하는 바람에 시간이 좀 걸리게 되었다.

 

1, 2, 3을 순서대로 대입해주는 방식으로 문제를 풀면 만들어낸 수열의 길이가 n일 경우 바로 출력하는 것이 가장 수가 적은 상태가 된다.

그래서 바로 출력해주고 끝내면 되는데, 이 부분을 다 구해보면서 비교해서 시간초과가 나왔었다. 필요 없는 코드들을 다 지워버리니 바로 통과했다.

 

주석 처리한 부분은 PyPy로도 한 번 돌려봤는데 런타임 에러가 떠서 sys.exit()으로 exit을 사용해준 것이었다.

Python으로 짧은 시간에 통과한 문제들은 PyPy로 굳이 돌려보지 않았는데 이번에 돌려보니 Python으로 시간이 짧게 걸린 코드가 PyPy에서는 그만큼의 성능이 나오지 않아서 신기했다.

# from sys import exit
def solve(s, l):
    for d in range(1, l//2 + 1):
        a = int(s[l-d:])
        b = int(s[l-2*d:l-d])
        if a == b:
            return

    if l == n:
        print(int(s))
        exit()

    for i in ['1', '2', '3']:
        solve(s+i, l+1)

n = int(input())
solve('1', 1)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다