[백준]1563개근상 #dp#dfs

1. 풀이

처음엔 dfs만으로 완전탐색으로 문제를 풀었지만 시간초과. (소스코드1)

정답은 dp+dfs였다.

몇번을 풀었지만 어려운 dp & dfs문제..

​

[원리]

(1) 조건에 맞지 않으면

i. return 0으로 가지치기

(2) 조건에 맞으면

i. 끝까지가면 : return 1

ii. 방문한적이 있으면 return dp

iii. 방문한적이 없으면 재귀후 저장 dp저장.

핵심은 바로 ii.방문한적이 있으면 return dp를 하는것!

​

ex) 4일동안 지각을 한번, 결석을 연속1번 한 경우를 생각해보자.

만약 이를 DFS+DP(소스코드1)로 푼다면, 해당 경우를 만족하는 모든 경우(OLOA,LOOA,OOLA)에 대해서 한번만 끝까지 계산을 해주고 DP에 저장해놓은다음, 다음에 만났을때 DP값을 반환해주면 된다,

하지만 그냥 DFS로 풀면 3가지경우 모두에 대해서 끝까지 재귀를 돌아야 한다.

​

2. 소스코드

(1) 소스코드1 (dfs 시간초과)

import sys
sys.setrecursionlimit(10**6)

N=int(input())

def dfs(day,absent,late):
    #print(day)
    global ans
    if day==N:
        #print(word)
        ans+=1
        return
    #참석
    dfs(day+1,0,late)
    #지각
    if late==0:
        dfs(day+1,0,late+1)
    #결석
    if absent!=2:
        dfs(day+1,absent+1,late)
        
ans=0
dfs(0,0,0)
print((ans)%1000000)

 

(2) 소스코드2 (dfs+dp, 통과)

import sys
sys.setrecursionlimit(10**6)

N=int(input())

dp=[[[-1 for absent in range(3)] for late in range(2)] for day in range(N+1)]
def dfs(day,late,absent):
    # 지각2번 or 결석연속3번
    if late==2 or absent==3:
        return 0
    # 개근을한 경우
    if day==N:
        return 1

    if dp[day][late][absent]==-1:
        # 참석 + 지각 + 결석
        attend=dfs(day+1,late,0)+dfs(day+1,late+1,0)+dfs(day+1,late,absent+1)
        dp[day][late][absent]=attend

        return attend
    else:
        return dp[day][late][absent]
            
ans=0
print((dfs(0,0,0))%1000000)