[파이썬] 백준 1563 개근상

우선은 product 로 접근을 했고 당연히 메모리 초과가 나왔다. 다음은 리스트에 중첩해서 쌓는 방식으로 했는데 이 역시도 메모리 초과가 나왔다. 그래서 재귀함수를 이용한 리스트 체크를 반복하는 걸로 구현했는데 이는 시간 초과가 나왔다.

 

dp 를 이용해서 푸는 문제였고, 이를 알기는 했는데 어떻게 할지 몰라서 구현을 못했다. 아래와 같은 방식이라고 한다.

 

import sys
from itertools import product
import math
 
# product 실패
sys.setrecursionlimit(10 ** 7)
a = ['O','L','A']
 
num = int(input())
 
def check(k):
    if k.count('L')>=2:
        return False
 
    for i in range(0,len(k)-2):
        if k[i]=='A' and k[i+1]=='A' and k[i+2] == 'A':
            return False
 
    return True
 
 
answer = 0
 
def re(k):
    if len(k)== num:
 
        global answer
 
        answer+=1
    else:
 
        if check(k+['L']) == True:
            re(k+['L'])
        if check(k+['O']) == True:
            re(k+['O'])
        if check(k+['A']) == True:
            re(k+['A'])
 
 
 
 
re(['O'])
re(['L'])
re(['A'])
 
print(answer)