[백준] 1669번: 멍멍이 쓰다듬기

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

INITIAL

I tried solving via DFS backtracking. BTW im still confused as to how to increment count in recurisve DFS without it overriding my count valeu.

my initial attempt where count is overriden:

def dfs(node , interval):
    count = 1
    moves = [interval-1,interval,interval+1]
    visited[node]=True
    if node == m-1:
        ans.append(count)
        return
    for move in moves:
        if node+move>=m:
            continue
        if not visited[node+move]:
            dfs(node+move, interval+1)
            count+=1
            visited[node+move]=False
            count-=1
dfs(n+1, 1)
print(max(ans))

corrected code:

n,m= map(int,input().split())
visited= [False for _ in range(m+1)]
visited[n+1]=True
ans = []

def dfs(node , interval, count):
    moves = [interval-1,interval,interval+1]
    visited[node]=True
    if node == m-1:
        ans.append(count)
        return
    for move in moves:
        if node+move>=m:
            continue
        if not visited[node+move]:
            count+= 1
            dfs(node+move, interval+1, count)
            visited[node+move]=False
            count-= 1
dfs(n+1, 1, 2)
print(min(ans))

but it resulted in memoryError.

There is actually a mathematical way to solve this.