https://www.acmicpc.net/problem/1563
initial
I tried optimising my dfs backtrackign as much as possible but it is not enough. But my solution is right if they allow like 10s for runtime lol
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n = int(input())
ans = 0
tmp = ''
moves = ['O', 'L', 'A']
def dfs():
global tmp, ans
if len(tmp) == n:
countL, countA = 0, 0
flag = False
for i in range(len(tmp)):
if flag:
break
if tmp[i] == 'L':
countL += 1
if countL >= 2:
flag = True
break
elif tmp[i] == 'A':
countA += 1
if tmp[i - 2:i + 1].count('A') == 3:
flag = True
break
else:
countA = tmp[i - 2:i + 1].count('A')
if not flag:
ans += 1
return
for a in moves:
tmp += a
dfs()
tmp = tmp[:-1]
dfs()
print(ans%1000000)solution
Since we are gonna have multiple visits to the same combination of values like OOLA, we should use dfs+dp to optimise the solution. Our dp solution is n time but my previous dfs solution, no matter how much I try to optimise by breaking out of loop once condition is met, is 3^n because we have 3 choices - absent,late or on time.
I should really train to think this way instead of global ans way. For the solution, parameters of day,late and absent are passed and they will be used to check for the condition whether or not it is valid or not. But my solution made a string and checked the conditions by iterating each character of the string, which is more troublesome and prone to mistakes.
If the correct condition is not met we return 0.
If we have correct condition, it means we skipped this ^ above condition so when day==n we return 1.
When we havent visited this dp grid (i.e. dp[cur_day][late][absent]==-1), we compute 3 choices
If we are on time, we dont have to add 1 to late or absent. So we just increment cur_day by 1. But how do we display absent parameter? We should put 0 as absent because This is important and tricky to think of. You need 3 consecutive absences. Since we are not absent, the absent parameter has to be defaulted to 0.
If we are late, we have to add 1 to late. Same here absent parameter should be defaulted to 0.
When we are absent, we carry forward our absent value and put absent+1 as parameter for the next dfs.
solution:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n = int(input())
dp = [[[-1 for _ in range(3)] for _ in range(2)] for _ in range(n)]
def dfs(day, late, absent):
if late == 2 or absent == 3:
return 0
elif day == n:
return 1
if dp[day][late][absent] == -1:
val = (
dfs(day + 1, late, 0)
+ dfs(day + 1, late + 1, 0)
+ dfs(day + 1, late, absent + 1)
)
dp[day][late][absent] = val
return val
else:
return dp[day][late][absent]
print(dfs(0, 0, 0) % 1000000)complexity
my dfs backtracking is 3^n as mentioned but this dp approach is n time.
ex) 4일동안 지각을 한번, 결석을 연속1번 한 경우를 생각해보자.
만약 이를 DFS+DP(소스코드1)로 푼다면, 해당 경우를 만족하는 모든 경우(OLOA,LOOA,OOLA)에 대해서 한번만 끝까지 계산을 해주고 DP에 저장해놓은다음, 다음에 만났을때 DP값을 반환해주면 된다,
하지만 그냥 DFS로 풀면 3가지경우 모두에 대해서 끝까지 재귀를 돌아야 한다.
